Dominique Foata

Guo-Niu Han

En Hommage

Pierre Rosenstiehl

Lui

Seidel Triangle Sequences and Bi-Entringer Numbers

Keywords: Entringer numbers, Poupard numbers, Bi-Entringer numbers, tangent numbers, secant numbers, alternating permutations, Seidel matrices, Seidel triangle sequences, greater neighbor statistic. Mathematics Subject Classifications. 05A15, 05A30, 11B68, 33B10

This Seidel Triangle Sequence Calculus makes it possible to derive several three-variate generating functions, in particular for the Bi-Entringer numbers, which count the alternating permutations according to their lengths, first and last letters. The paper has been motivated by this suprising observation: the number of alternating permutations, whose last letter has a prescribed value and is greater than its first letter, is equal to the Poupard number.

Introduction

As they have been reinterpreted in our previous paper [START_REF] Foata | Finite Difference Calculus for Alternating Permutations[END_REF], the Poupard numbers g n (k) and h n (k) for n ≥ 1, 1 ≤ k ≤ 2n -1 can be defined as the coefficients in the following expansions

1 + n≥1 1≤k≤2n+1 g n+1 (k) x 2n+1-k (2n + 1 -k)! y k-1 (k -1)! = cos(x -y) cos(x + y) ; (1.1) 1 + n≥1 1≤k≤2n+1 h n+1 (k)
x 2n+1-k (2n + 1 -k)! y k-1 (k -1)! = cos(x -y) cos 2 (x + y) . (1.2) They are refinements of the tangent and secant numbers k g n (k) = T 2n-1 (n ≥ 1), (1.3) k h n (k) = E 2n (n ≥ 1), (1.4) which are themselves the coefficients of the Taylor expansions of tan u and sec u:

tan u = n≥1 u 2n-1 (2n -1)! T 2n-1 = u 1! 1+ u 3 3! 2+ u 5 5! 16+ u 7 7! 272+ u 9 9! 7936+• • • sec u = n≥0 u 2n (2n)! E 2n = 1+ u 2 2! 1+ u 4 4! 5+ u 6 6! 61+ u 8 8! 1385+ u 10 10! 50521+• • •
(See, e.g., [START_REF] Nielsen | Traité élémentaire des nombres de Bernoulli[END_REF], [START_REF] Comtet | Advanced Combinatorics[END_REF]).

Several combinatorial models have been introduced to interpret the Poupard numbers: see [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF][START_REF] Foata | Finite Difference Calculus for Alternating Permutations[END_REF][START_REF] Foata | Tree Calculus for Bivariate Difference Equations[END_REF][START_REF] Foata | Secant Tree Calculus, to appear in Central Europ[END_REF]. The first numerical values of those numbers are displayed in Fig. 1.1-2. According to Désiré André [An1879, An1881] each permutation w = x 1 x 2 • • • x n of 12 • • • n is said to be (increasing) alternating if x 1 < x 2 , x 2 > x 3 , x 3 < x 4 , etc. in an alternating way. Let Alt n be the set of all alternating permutations of 12 • • • n. He then proved that # Alt n = T n (resp. = E n ), if n is odd (resp. even). Let F w := x 1 and L w := x n be the first and last letters of a permutation w = x 1 x 2 • • • x n of 12 • • • n.

The numbers E n (m) := #{w ∈ Alt n : F w = m}, now called Entringer numbers, were introduced by Entringer himself [START_REF] Entringer | A combinatorial interpretation of the Euler and Bernoulli numbers[END_REF], who derived their main combinatorial and arithmetical properties. Those numbers are registered as the A008282 sequence in Sloane's On-Line Encyclopedia of Integer Sequences, together with an abundant bibliography [Sl]. They naturally constitute another refinement of the tangent and secant numbers. Their first values are shown in Fig. 1 We have been led to introduce the Bi-Entringer numbers, defined by

(1.5) E n (m, k) := #{w ∈ Alt n : F w = m, L w = k}, first, to see whether we could obtain a closed form for their generating function, second, to understand why, and prove that, over the set Alt 2n-1 and given the event {F < L}, the conditional probability that F = k is equal to g n (k)/T 2n-1 , where g n (k) is the Poupard number defined in (1.1).

In Section 5 we shall give two proofs of the latter statement (see Theorem 1.2), a combinatorial one and also an analytic one using the Laplace transform. Now, to derive the generating function for the Bi-Entringer numbers a study of the so-called Seidel Triangle Sequences is to be made and will be developed in Section 2. Roughly speaking, Seidel's memoir [Se1877], as was superbly reactivated by Dumont [START_REF] Dumont | Matrices d'Euler-Seidel[END_REF], establishes a connection between several sequences of classical numbers and polynomials, by means of a finite difference calculus displayed in matrix form. The method is to be enlarged when dealing with sequences of matrices instead of sequences of numbers. It will be seen that with each Seidel Triangle Sequence can be associated an explicit form for its generating function (Theorem 2.2).

The Bi-Entringer numbers, displayed as entries of matrices M n := (E n (m, k)) 1≤m,k≤n (see Fig. 1.4) give rise to four Seidel Triangle Sequences: the sequences of the upper (resp. lower) triangles of the matrices M n , for n odd and for n even. It will be shown that each matrix M n for n odd is symmetric with respect to its diagonal, so that it suffices, when n is odd, to give the expression of the generating function for the upper triangles, as stated in the next theorem.

Theorem 1.1. The generating functions for the coefficients E n (m, k) are given by

(1.6) 1≤m+1≤k≤2n-1 E 2n (m + 1, k + 1) x 2n-k-1 (2n -k -1)! y k-m-1 (k -m -1)! z m m! = cos x cos z cos(x + y + z) ; (1.7) 1≤m+1≤k≤2n-1 E 2n (k + 1, m + 1) x 2n-k-1 (2n -k -1)! y k-m-1 (k -m -1)! z m m! = sin x sin z cos(x + y + z) ; (1.8) 1≤m+1≤k≤2n E 2n+1 (m + 1, k + 1) x 2n-k (2n -k)! y k-m-1 (k -m -1)! z m m! = sin x cos z cos(x + y + z) .
Theorem 1.1 will be proved in Section 3, once the main arithmetical properties of the Bi-Entringer numbers are given. The first values of the Bi-Entringer numbers are displayed in Fig. 1.4, as entries of the matrices

M n := (E n (m, k)) 1≤m,k≤n . M 1 = 1 1 1 ; M 2 = 1 2 1 . 1 2 . . ; M 3 =    1 2 3 1 . 1 . 2 1 . . 3 . . .    ; M 4 =       1 2 3 4 1 . 0 1 1 2 . . 1 1 3 . 1 . 0 4 . . . .       ; M 5 =         1 2 3 4 5 1 . 2 2 1 . 2 2 . 2 1 . 3 2 2 . 0 . 4 1 1 0 . . 5 . . . . .         ; M 6 =        . 0 2 4 5 5 . . 2 4 5 5 . 2 . 4 4 4 . 2 4 . 2 2 . 1 2 2 . 0 . . . . . .        ; M 7 =         
. Further arithmetical properties of the Bi-Entringer numbers, in particular involving binomial coefficients, will be given in Section 4. There is also a linear connection between Poupard and Bi-Entringer numbers, as stated in the next theorem, which is proved in Section 5.

Theorem 1.2. For 2 ≤ k ≤ 2n we have:

(1.9) 2 k m=1 E 2n+1 (m, k) = g n+1 (k).
The specialization of identities (1.6) and (1.8) for z = 0 provides an expression for the generating function for the Entringer numbers E n (m) themselves, apparently nowhere obtained, to our knowledge. The calculation is banal: just note that

E 2n (1, k + 1) = E 2n-1 (2n -k) and E 2n+1 (1, k + 1) = E 2n (k).
Corollary 1.3. We have

1≤k≤2n-1 E 2n-1 (k) x k (k -1)! y 2n-k-1 (2n -k -1)! = cos x cos(x + y) ; (1.10) 1≤k≤2n E 2n (k) x 2n-k (2n -k)! y k-1 (k -1)! = sin x cos(x + y) . (1.11)
Although the Poupard numbers h n (k), defined in (1.2), will not be further considered in this paper, it was important to mention that the pairs (g n (k), h n (k)) and (E 2n-1 (k), E 2n (k)) form two refinements of the pairs (T 2n-1 , E 2n ) having analogous generating function displayed in (1.1), (1.2), (1.10), (1.11).

Seidel Triangle Sequences

Throughout the paper the following exponential generating functions will be attached to each infinite matrix A = (a(m, k)) m,k≥0

A(x, y) := m,k≥0 a(m, k) x m m! y k k! ; A m,• (y) := k≥0 a(m, k) y k k! ; A •,k (x) := m≥0 a(m, k) x m m! ;
for A itself, its m-th row, its k-th column. As can be found in [START_REF] Dumont | Matrices d'Euler-Seidel[END_REF], a Seidel matrix A = (a(m, k)) (m, k ≥ 0) is defined to be an infinite matrix, whose entries belong to some ring, and obey the following rules: (SM1) the sequence of the entries from the top row a(0, 0), a(0, 1), a(0, 2), . . . is given; it is called the initial sequence;

(SM2) for m ≥ 1 and k ≥ 0 the following relation holds:

a(m, k) = a(m -1, k) + a(m -1, k + 1).
The entries of the Seidel matrix A can be obtained by applying rule (SM2) inductively, starting with the initial sequence. The leftmost column a(0, 0), a(1, 0), a(2, 0), . . . is called the final sequence. As stated in the next proposition, the exponential generating functions for the final sequence A •,0 (x) and for the Seidel matrix itself A(x, y) can be derived from the generating function A 0,• (y) for the initial sequence. See, e.g., [START_REF] Dumont | Matrices d'Euler-Seidel[END_REF][START_REF] Dumont | A combinatorial interpretation of the Seidel generation of Genocchi numbers, Combinatorial mathematics[END_REF].

Proposition 2.1. Let A = (a i,j ) (i, j ≥ 0) be a Seidel matrix. Then,

A •,0 (x) = e x A 0,• (x) and A(x, y) = e x A 0,• (x + y).
As noted by Dumont [START_REF] Dumont | Matrices d'Euler-Seidel[END_REF], the following example of a Seidel matrix, denoted by H = (h i,j ) i,j≥0 , goes back to Seidel himself [Se1877]. The initial sequence consists of the sequence of the coefficients of the Taylor expansion of 1 -tanh u = 2/(1 + e 2u ), that is, 1, -1, 0, 2, 0, -16, 0, 272, 0, . . . so that

H 0,• (y) = 1 -tanh y = 1 + n≥1 y 2n-1 (2n -1)! (-1) n T 2n-1 = 1 - y 1! 1+ y 3 3! 2- y 5 5! 16+ y 7 7! 272- y 9 9! 7936+• • • It follows from Proposition 2.1 that (2.1) H •,0 (x) = 1 cosh x = 2 e x 1 + e 2x ; H(x, y) = 2 e x 1 + e 2x+2y ;
and the matrix H itself reads: (2.2)

H =                 1 -1 0 2 0 -16 0 272 0 • • • 0 -1 2 2 -
                .
The Entringer numbers E n (m) mentioned in the introduction appear as entries of the matrix H, displayed along the counter-diagonals with a given sign. In fact, we have the relation

(2.3) h i,j = (-1) n E i+j+1 (j + 1), if i + j = 2n; (-1) n E i+j+1 (i + 1), if i + j = 2n -1; as can be verified by induction, or still (2.4) E 2n+1 (j + 1) = (-1) n h 2n-j,j (0 ≤ j ≤ 2n); (2.5) E 2n (i + 1) = (-1) n h i,2n-1-i (0 ≤ i ≤ 2n -1).
The matrix H will be given a key role in Section 3.

We now come to the main definition of this section. A sequence of square matrices (A n ) (n ≥ 1) is called a Seidel triangle sequence if the following three conditions are fulfilled:

(STS1) each matrix A n is of dimension n;

(STS2) each matrix A n has null entries along and below its diagonal; let (a n (m, k) (0 ≤ m < k ≤ n -1) denote its entries strictly above its diagonal, so that

A 1 = ( • ) ; A 2 = • a 2 (0, 1) • • ; A 3 =   • a 3 (0, 1) a 3 (0, 2) • • a 3 (1, 2) • • •   ; . . . ; A n =         • a n (0, 1) a n (0, 2) • • • a n (0, n -2) a n (0, n -1) • • a n (1, 2) • • • a n (1, n -2) a n (1, n -1) . . . . . . . . . . . . . . . . . . • • • • • • a n (n -3, n -2) a n (n -3, n -1) • • • • • • • a n (n -2, n -1) • • • • • • • •         ;
the dots "•" along and below the diagonal referring to null entries. (STS3) for each n ≥ 2, the following relation holds:

a n (m, k) -a n (m, k + 1) = a n-1 (m, k) (m < k).
Record the last columns of the triangles A 2 , A 3 , A 4 , A 5 , . . . , read from top to bottom, namely, a 2 (0, 1); a 3 (0, 2), a 3 (1, 2); a 4 (0, 3), a 4 (1, 3), a 4 (2, 3); a 5 (0, 4), a 5 (1, 4), a 5 (2, 4), a 5 (3, 4); . . . as counter-diagonals of an infinite matrix H = (h i,j ) i,j≥0 , as shown next:

(2.6) H :=          0 1 2 3 4 0 a 2 (0, 1) a 3 (1, 2) a 4 (2, 3) a 5 (3, 4) a 6 (4, 5) • • • 1 a 3 (0, 2) a 4 (1, 3) a 5 (2, 4) a 6 (3, 5) 2 a 4 (0, 3) a 5 (1, 4) a 6 (2, 5) 3 a 5 (0, 4) a 6 (1, 5) 4 a 6 (0, 5) . . .          ,
In an equivalent manner, the entries of H are defined by:

(2.7) h i,j = a i+j+2 (j, i + j + 1).

The next theorem shows that the three-variable generating function for a Seidel triangle sequence, when suitably normalized, can be expressed in a very closed form.

Theorem 2.2. The three-variable generating function for the Seidel triangle sequence

(A n = (a n (m, k))) n≥1 is equal to 1≤m+1≤k≤n-1 a n (m, k) x n-k-1 (n -k -1)! y k-m-1 (k -m -1)! z m m! = e x H(x + y, z),
where H is the infinite matrix defined in (2.7).

Proof. We set up a sequence of infinite matrices (Ω (p) = ((ω

(p) i,j ) i,j≥0
)) (p ≥ 0) that record the rows of the matrices A n in the following manner

Ω (p) =     a p+2 (p, p + 1) a p+3 (p, p + 2) a p+4 (p, p + 3) • • • a p+3 (p, p + 1)
Ω (p) (x, y) = e x Ω (p) 0,• (x + y). Define: Ω(x, y, z) := p≥0 z p p! Ω (p) (x, y). Then, Ω(x, y, z) = p≥0 z p p! Ω (p) (x, y) = p≥0 z p p! e x Ω (p) 0,• (x + y) = e x H(x + y, z).
On the other hand,

Ω(x, y, z) = p≥0 z p p! Ω (p) (x, y) = i,j,p≥0 z p p! x i i! y j j! ω (p) i,j = i,j,p≥0 z p p! x i i! y j j! a p+i+j+2 (p, p + j + 1).
With the change of variables p + i + j + 2 = n, p = m, p + j + 1 = k, we then get

Ω(x, y, z) = 1≤m+1≤k≤n-1 a n (m, k) x n-k-1 (n -k -1)! y k-m-1 (k -m -1)! z m m! .
This completes the proof of Theorem 2.2.

The Bi-Entringer numbers

Before proving Theorem 1.1 we give a list of properties involving the Bi-Entringer numbers. The celebrated identities à la boustrophedon (see [MSY96], and [Ro13, p. 95-101] for a more literary approach) satisfied by the Entringer numbers E n (m) can be extended over to the Bi-Entringer numbers E n (m, k), as stated in relations (3.1)-(3.4) below.

Proposition 3.1. We have:

(i) E n (m, m) = 0 for all m and E n (n, k) = 0 for all k and n ≥ 2;

(ii) for n odd and

1 ≤ k, m ≤ n E n (m, k) = n-1 j=k E n-1 (m, j) if m < k; (3.1) E n (m, k) = n-1 j=k E n-1 (m -1, j) if m > k. (3.2)
In particular, E n (n -2, n -1) = 0 for n ≥ 5; E n (m, n) = 0 for all n, m.

(iii) For n even and 1 ≤ m, k ≤ n we further have:

E n (m, k) = k-1 j=1 E n-1 (m, j) if m < k; (3.3) E n (m, k) = k-1 j=1 E n-1 (m -1, k) if m > k. (3.4)
In particular, E n (n -1, n) = 0 when n ≥ 4; E n (i, 1) = 0 for all i.

(iv) Each matrix M n is symmetric with respect to its diagonal (resp. its counter-diagonal), whenever n is odd (resp. even), that is,

E n (m, k) = E n (k, m), when n is odd, E n (n + 1 -k, n + 1 -m), when n is even. (3.5) Moreover, k E n (m, k) = E n (m) (n ≥ 1); (3.6) m E n (m, k) = E n (k), when n is odd; E n (n + 1 -k), when n is even.
The proofs of all those properties are easy, by simple manipulations; in particular, (3.5) by using the basic dihedral transformations on alternating permutations. They are omitted.

Proposition 3.2 (The finite difference relations). We have:

(3.7) E n (m, k) -E n (m, k + 1) = (-1) n-1 E n-1 (m, k), if 1 ≤ m < k ≤ n -1; (3.8) E n (m, k) -E n (m, k + 1) = (-1) n-1 E n-1 (m -1, k), if 2 ≤ k + 1 < m ≤ n.
Proof. The two identities can be proved by simple iterations of (3.1)-(3.4). Alternatively, we can also proceed as follows. Let m Alt n k (resp. m Alt n l k) designate the number of all σ from Alt n starting with m and ending with k (resp. ending with the right factor l k). We have: By Proposition 3.2, the sequence (W n ) is a Seidel triangle sequence, and the corresponding matrix H, defined by (2.6)-(2.7), is equal to

m Alt n k -m Alt n (k + 1) = -m Alt n k (k + 1), if n is even; m Alt n (k + 1) k, if n is odd. Next, if n is even, -m Alt n k (k + 1) = -m Alt n-1 k, if 1 ≤ m < k ≤ n -1; -(m -1) Alt n-1 k, if 2 ≤ k + 1 < m ≤ n; and if n is odd, m Alt n (k + 1) k = m Alt n-1 k, if 1 ≤ m < k ≤ n -1; (m -1) Alt n-1 k, if 2 ≤ k + 1 < m ≤ n.
W 1 = 0 0 • ; W 2 = 0 1 0 . 1 1 . . ; W 3 =   0 1 2 0 . 1 . 1 . . . 2 . . .   ; W 4 =     0 1 2 3 0 . 0 -1 -1 1 . . -1 -1 2 . . . 0 3 . . . .     ; W 5 =       0 1 2 3 4 0 . -2 -2 -1 . 1 . . - 2
H =        0 1 2 3 4 5 0 e 2 (0, 1) • e 4 (2, 3) • e 6 (4, 5) • • • • 1 • e 4 (1, 3) • e 6 (3, 5) • 2 e 4 (0, 3) • e 6 (2, 5) • 3 • e 6 (1, 5) • 4 e 6 (0, 5) • 5 • . . .       
, the "dots" being written in place of 0's. Note that all the counter-diagonals e 2n+1 (0, 2n), e 2n+1 (1, 2n), . . . , e 2n+1 (2n -1, 2n), which are equal to the last columns of the W 2n+1 's, have null entries. It then remains to evaluate e 2n (m, 2n -1) for 0 ≤ m ≤ 2n -1. By (3.9) we have: e 2n (m, 2n -1) = (-1) n+1 E 2n (m + 1, 2n). But E 2n (m + 1, 2n) is equal to the Entringer number E 2n-1 (m + 1), as each alternating permutation σ from Alt 2n such that F σ = m + 1 and L σ = 2n can be mapped onto a permutation from Alt 2n-1 starting with (m + 1) by simply deleting the last letter (2n), and this in a bijective manner.

Now, by (2.4), E

2n-1 (m+1) = E 2(n-1)+1 (m+1) = (-1) n-1 h 2n-2-m,m for 0 ≤ m ≤ 2n -2. Altogether, (3.11) e 2n (m, 2n -1) = h 2n-2-m,m (0 ≤ m ≤ 2n -2),
that is, by (2.2),

H =           1 • 0 • 0 • 0 • • • • • -1 • 2 • -16 • -1 • 4 • -32 • • 5 • -46 • 5 • -56 • • -61 • -61 • • . . .           .
Thus, H is obtained from the matrix H, displayed in (2.2), by replacing all the entries h i,j such that i + j is odd by zero. By (2.1) we have H(x, y) = 2e x 1 + e 2x+2y , so that (3.12) H(x, y) = H(x, y) + H(-x, -y) 2 = e x 1 + e 2y 1 + e 2x+2y .

Let

(3.13) Ω(x, y, z)

= 1≤m+1≤k≤n-1 e n (m, k) x n-k-1 (n -k -1)! y k-m-1 (k -m -1)! z m m! .
be the three-variate generating function for the e n (m, k)'s. By Theorem 2.2 (3.14) Ω(x, y, z) = e x H(x + y, z) = e 2x+y 1 + e 2z 1 + e 2x+2y+2z .

With I := √ -1 equation (3.13) reads:

Ω(xI, yI, zI) = 1≤m+1≤k≤n-1 I n-2 e n (m, k) x n-k-1 (n -k -1)! y k-m-1 (k -m -1)! z m m! .
But, by (3.9) and (3.10)

I 2n-2 e 2n (m, k) = E 2n (m + 1, k + 1); I 2n-1 e 2n+1 (m, k) = IE 2n+1 (m + 1, k + 1). Therefore, Ω(xI, yI, zI) = 1≤m+1≤k≤2n-1 E 2n (m + 1, k + 1) x 2n-k-1 (2n -k -1)! y k-m-1 (k -m -1)! z m m! + I 1≤m+1≤k≤2n E 2n+1 (m + 1, k + 1) x 2n-k (2n -k)! y k-m-1 (k -m -1)! z m m! .
Next, (3.14) becomes:

Ω(xI, yI, zI) = e 2xI+yI 1 + e 2zI 1 + e 2xI+2yI+2zI = e xI e -zI + e zI e -xI-yI-zI + e xI+yI+zI = (cos(x) cos(z) + I sin(x) cos(z))/ cos(x + y + z).

By comparing the above two identities for Ω(xI, yI, zI), we obtain (1.6) and (1.8) in Theorem 1.1.

To prove (1.7) in Theorem 1.1 let (W ′ n ) = (e ′ n (m, k)) be the sequence of matrices obtained from (M n ) = (E n (m, k)) by the following modifications:

(W ′ 1) W ′ 1 := (0); (W ′ 2) W ′ n := M r n for n ≡ 1, 2 (mod 4
) and n ≥ 2, where M r n is obtained from M n by performing a rotation by 180 o about its center;

(W ′ 3) W ′ n := (-1)M r n for n ≡ 0, 3 (mod 4); (W ′ 4) delete the lower triangle of each matrix W ′ n ; (W ′ 5) start labelling from 0, 1, 2, . . . In other words, for m < k define the normalized Bi-Entringer numbers e ′ n (m, k) to be:

e ′ 2n (m, k) = (-1) n+1 E 2n (2n -m, 2n -k); (3.15) e ′ 2n+1 (m, k) = (-1) n E 2n+1 (2n + 1 -m, 2n + 1 -k). (3.16)
The first values of the W ′ n are shown in Fig. 3.2.

W ′ 1 = 0 0 • ; W ′ 2 = 0 1 0 . 0 1 . . ; W ′ 3 =   0 1 2 0 . 0 . 1 . . -1 2 . . .   ; W ′ 4 =     0 1 2 3 0 . 0 0 0 1 . . -1 0 2 . . . 0 3 . . . .     ; W ′ 5 =       0 1 2 3 4 0 . . . . . 1 . . 0 1 1 2 . . . 2 2 3 . . . . 2 4 . . . . .       ;     . 0 0 0 0 0 . .
H ′ = (h ′ i,j
), is equal to:

H ′ =         0 1 2 3 4 5 0 • e ′ 3 (1, 2) • e ′ 5 (3, 4) • e ′ 7 (5, 6) • • • 1 e ′ 3 (0, 2) • e ′ 5 (2, 4) • e ′ 7 (4, 6) 2 • e ′ 5 (1, 4) • e ′ 7 (3, 6) 3 e ′ 5 (0, 4) • e ′ 7 (2, 6) 4 • e ′ 7 (1, 6) 5 e ′ 7 (0, 6) . . .         .
Its counter-diagonals e ′ 2n (0, 2n -1), e ′ 2n (1, 2n -1), . . . , e ′ 2n (2n -2, 2n -1) have null entries, as it is so for the last columns of the W ′ 2n 's. Furthermore, e ′ 2n+1 (m, 2n) = h 2n-m-1,m (0 ≤ m ≤ 2n -1) by (2.5) and (3.16), so that

H ′ =          • -1 • 2 • -16 • • • • 0 • 2 • -16 • • 1 • -14 • 0 • -10 • • -5 • 0 • • . . .          ,
which is derived from H by replacing the entries h i,j such that i + j is even by 0. Therefore,

H ′ (x, y) = H(x, y) -H(-x, -y) 2 = e x 1 -e 2y 1 + e 2x+2y . Let Ω ′ (x, y, z) = 1≤m+1≤k≤n-1 e ′ n (m, k) x n-k-1 (n -k -1)! y k-m-1 (k -m -1)! z m m! . ( 3
.17) be the generating function for the e ′ n (m, k)'s. By Theorem 2.2

Ω ′ (x, y, z) = e x H ′ (x + y, z) = e 2x+y 1 -e 2z 1 + e 2x+2y+2z . (3.18) Then, Ω ′ (xI, yI, zI) = 1≤m+1≤k≤n-1 I n-2 e n (m, k) x n-k-1 (n -k -1)! y k-m-1 (k -m -1)! z m m! .
By (3.15) and (3.16)

I 2n-2 e ′ 2n (m, k) = E 2n (2n -m, 2n -k); I 2n-1 e ′ 2n+1 (m, k) = -I E 2n+1 (2n + 1 -m, 2n + 1 -k). Therefore, Ω ′ (xI, yI, zI) = 1≤m+1≤k≤2n-1 E 2n (2n -m, 2n -k) x 2n-k-1 (2n -k -1)! y k-m-1 (k -m -1)! z m m! -I 1≤m+1≤k≤2n E 2n+1 (2n + 1 -m, 2n + 1 -k) x 2n-k (2n -k)! y k-m-1 (k -m -1)! z m m! .
On the other hand, (3.18) becomes:

Ω ′ (xI, yI, zI) = e 2xI+yI
1 -e 2zI 1 + e 2xI+2yI+2zI = e xI e -zI -e zI e -xI-yI-zI + e xI+yI+zI = (sin(x) sin(z) -I cos(x) sin(z))/ cos(x + y + z).

Compare the above two identities for Ω(xI, yI, zI) and use (3.6). This proves (1.8) in Theorem 1.1, and yields another proof of the identity

E 2n+1 (m, k) = E 2n+1 (k, m).

Row sums with binomial coefficients

We next show that the closed forms for the generating functions for the Bi-Entringer numbers derived in (1.6)-(1.8) provide several identities for the numbers themselves, all involving binomial coefficients.

Proposition 4.1. We have:

2n k=m (-1) k 2n k k m E 2n+2 (m + 1, k + 2) = (-1) n χ(m = 0).
Proof. Identity (1.6) may be rewritten as:

(4.1) 0≤m≤k≤2n z m m! x 2n-k (2n -k)! y k-m (k -m)! E 2n+2 (m+1, k +2) = cos(x) cos(z) cos(x + y + z) .
With y = -x and z = -xz identity (4.1) becomes:

(4.2) 0≤m≤k≤2n z m m! x 2n (2n -k)! (-1) k (k -m)! E 2n+2 (m+1, k+2) = cos(x) cos(-xz) cos(-xz) .
Let α n (m) be the left-hand side of the identity to prove. Then, (4.2) can be expressed as:

n,m≥0 z m x 2n (2n)! α n (m) = cos(x).
Example. n = 2. m = 1 :

- 4 1 1 1 2+ 4 2 2 1 4- 4 3 3 1 5+ 4 4 4 1 5 = -8+48-60+20 = 0; m = 0 : + 4 0 0 - 4 1 2 + 4 2 4 - 4 3 5 + 4 4 5 = 0 -8 + 24 -20 + 5 = 1.
Proposition 4.2. We have

2n k=m (-1) k 2n k k m E 2n+2 (k + 2, m + 1) = (-1) n-(m-1)/2 2n m T m ,
with the convention that T m = 0, if m is even, and equal to the tangent number T m otherwise.

Proof. Rewrite identity (1.7) as

(4.3) 0≤m≤k≤2n z m m! x 2n-k (2n -k)! y k-m (k -m)! E 2n+2 (k +2, m+1) = sin(x) sin(z) cos(x + y + z) ,
and let y = -x and z = -xz in (4.3), to get:

(4.4) 0≤m≤k≤2n z m m! x 2n (2n -k)! (-1) k (k -m)! E 2n+2 (k+2, m+1) = sin(x) sin(-xz) cos(-xz) .
Let α n (m) be the left-hand side of the identity to be proved. Then, n,m≥0

z m x 2n (2n)! α n (m) = -sin(x) tan(xz) = -sin(x) m T m (xz) m m! . Hence, n≥0 x 2n (2n)! α n (m) = -sin(x)T m x m m! = k≥0 (-1) k+1 x 2k+1 (2k + 1)! T m x m m! .
Example. n = 3. m = 1 :

-

(-1) k 2n -1 k k m E 2n+1 (m + 1, k + 2) = (-1) n+1 χ(m = 0).
Proof. Rewrite identity (1.8) as

(4.5) 0≤m≤k≤2n-1 z m m! x 2n-1-k (2n-1-k)! y k-m (k-m)! E 2n+1 (m+1, k +2) = sin(x) cos(z) cos(x+y+z) ;
and let y = -x and z = -xz in (4.5), to get:

0≤m≤k≤2n-1 z m m! x 2n-1 (2n -1 -k)! (-1) k (k -m)! E 2n+1 (m + 1, k + 2) = sin(x).
Then, (4.6)

0≤m≤k≤2n-1

z m m! 1 (2n -1 -k)! (-1) k (k -m)! E 2n+1 (m + 1, k + 2) = (-1) n+1 1 (2n -1)! .
Let α n (m) be the left-hand side of the identity to prove. By (4.6), α n (0) = (-1) n+1 and α n (m) = 0 for m ≥ 1.

Example. n = 3.

Proofs of Theorem 1.2

In section 4 we have derived several identities for the Bi-Entringer numbers all involving binomial coefficients, in contrast to identity (1.9) that linearly relates Poupard numbers to tangent numbers and Bi-Entringer numbers. The next analytical proof makes use of the Laplace transform

L(f (x), x, s) : = ∞ 0 f (x)e -xs dx,
which, in particular, maps x k /k! onto 1/s k+1 :

L( x k k! , x, s) = 1 s k+1 .
To illustrate this Laplace transform method we first give a proof of (1.3). Apply the Laplace transform twice to the left-hand side of (1.1), first, with respect to x, s, then to y, t. We get

1 + n≥1 1≤k≤2n+1 g n+1 (k) 1 t 2n+2-k 1 s k , an expression which becomes 1 + n≥1 1≤k≤2n+1 g n+1 (k) 1 s 2n+2
for s = t. We need prove that

1 + n≥1 1≤k≤2n+1 g n+1 (k) 1 s 2n+2 = 1 + n≥1 T 2n+1 1 s 2n+2 , which is equivalent to ∞ 0 ∞ 0 cos(x -y) cos(x + y) e -t(x+y) dx dy = ∞ 0 tan(x) e -tx dx.
But this identity is true, since by letting r = x + y: Analytical proof of Theorem 1.2. Start with identity (4.5), which is another form of (1.8) and apply the Laplace transform to its left-hand side three times with respect to (x, s), (y, t), (z, u), respectively. We get 0≤m≤k≤2n-1

1 u m+1 1 s 2n-k 1 t k-m+1 E 2n+1 (m + 1, k + 2), which becomes (5.1) 0≤m≤k≤2n-1 1 s 2n+2 1 t k+2 E 2n+1 (m + 1, k + 2),
when t ← st and u ← st. Apply the Laplace transform to the right-hand side of (4.5) three times with respect to (x, s), (y, t), (z, u), respectively, and let t ← st, u ← st. With r = y + z we get:

∞ 0 ∞ 0 ∞ 0 sin(x) cos(z) cos(x + y + z) e -xs-yst-zst dx dy dz = ∞ 0 ∞ 0 r 0 sin(x) cos(z) cos(x + r) e -xs-rst dz dr dx = ∞ 0 ∞ 0 sin(x) sin(r) cos(x + r) e -xs-rst dr dx = ∞ 0 ∞ 0 1 2 cos(x -r) cos(x + r) -1 e -xs-rst dr dx = 1 2 ∞ 0 ∞ 0 n≥1 1≤k≤2n+1 g n+1 (k) x 2n+1-k (2n + 1 -k)! r k-1 (k -1)! e -xs-rst dr dx = 1 2 n≥1 1≤k≤2n+1 g n+1 (k) 1 s 2n+2-k 1 (st) k = 1 2 n≥1 1≤k≤2n+1 g n+1 (k) 1 s 2n+2 1 t k . (5.2)
Then, (1.9) is a consequence of the identity (5.1)=(5.2).

Combinatorial proof of Theorem 1.2. We make use of the greater neighbor statistic "grn," which was defined in our previous paper [START_REF] Foata | Finite Difference Calculus for Alternating Permutations[END_REF] as follows: let σ = σ(1)σ(2) • • • σ(n) be an alternating permutation from Alt n , so that σ(i) = n for a certain i (1 ≤ i ≤ n). By convention, let σ(0) = σ(n + 1) := 0. Then, its definition reads: grn(σ) := max{σ(i -1), σ(i + 1)}. Let A2n+1 be the set of all decreasing alternating permutations of {1, 2, • • • , 2n+1}, i.e., permutations w = x 1 x 2 • • • x 2n+1 such that x 1 > x 2 , x 2 < x 3 , x 3 > x 4 , etc. and let A2n+1,k := {σ ∈ A2n+1 : grn(σ) = k}. It was proved in [START_REF] Foata | Finite Difference Calculus for Alternating Permutations[END_REF] (Theorem 1.4) that (5.3) g n+1 (k + 1) = # A2n+1,k .

For n ≥ 1 each set A2n+1,k can be split into two subsets of the same cardinality

A < 2n+1,k + A > 2n+1,k
, depending on whether the greater neighbor k is on the left, or on the right of (2n + 1).

On the other hand, let

G 2n+1,k := {σ ∈ Alt 2n+1 : L σ = k > F σ}
be the set of all increasing alternating permutations from Alt 2n+1 having their last letter equal to k and greater than their first letter. Then, each permutation

σ = x 1 • • • x j-1 (2n + 1)x j+1 • • • x 2n+1 from A < 2n+1,k , which is such that x j-1 = k > x j+1 can be mapped onto the permutation τ = (x j+1 + 1) • • • (x 2n+1 + 1) 1 (x 1 + 1) • • • (x j-1 + 1) from G 2n+1,k+1 in a bijective manner. Thus, #G 2n+1,k+1 = # A < 2n+1,k and 2 #G 2n+1,k+1 = # A < 2n+1,k +# A > 2n+1,k = # A2n+1,k , so that g n+1 (k + 1) = 2 #G 2n+1,k+1 = 2 l≤k E 2n+1 (k + 1, l),
as E 2n+1 (k + 1, k + 1) = 0. This implies identity (1.9) since E 2n+1 (m, l) = E 2n+1 (l, m) for all m, l (see Proposition 3.1(iv)).

Dumont [START_REF] Dumont | [END_REF] drew our attention to the following relation between Poupard and Bi-Entringer numbers, namely, (5.4)

g n (k) = 2 E 2n (k, k + 1) = 2 E 2n (k + 1, k).
Before giving a combinatorial proof of that identity we state and prove a property on alternating permutations, both increasing and decreasing, that involves the statistics F, L, and also two other statistics attached to the left f and right l neighbors of the maximum. Each permutation σ of 12 • • • n may be written

(5.5) σ = x 1 x 2 • • • x n = F(σ) • • • f(σ) max(σ) l(σ) • • • L(σ),
where F(σ) = x 1 , L(σ) = x n and, if max(σ) := n = x k , then f(σ) = x k-1 , l(σ) = x k+1 , where the convention x 0 = x n+1 = 0 still holds. For each finite word w = y 1 y 2 • • • y m , whose letters are integers, it is convenient to use the notation: (w + 1) := (y 1 + 1)(y 2 + 1) • • • (y m + 1), when w is not the empty word e, and e when it is.

Property 5.1. Let σ = w 1 max(σ)w 2 be a permutation of 12 • • • (2n -1), so that max(σ) = 2n -1. Then, the mapping φ 1 : w 1 max(σ) w 2 → w 2 max(σ) w 1 (5.6) is a bijection of Alt 2n-1 onto itself having the property (f, l)σ = (L, F)φ 1 (σ), (5.7) while the mapping φ 2 : w 1 max(σ) w 2 → (w 2 + 1) 1 (w 1 + 1) (5.8) is a bijection of A 2n-1 onto Alt 2n-1 having the property (f, l)σ = (L -1, F -1)φ 2 (σ).

(5.9)

The proof of Property 5.1 is straightforward. Just mention three examples: (i) φ 1 (3427561) = 5617342 and (f, l) (342 7 561) = (2, 5) = (L, F) (561 7 342); (ii) φ 2 (5471326) = 2437165 and (f, l)(54 7 1326) = (4, 1) = (L -1, F -1)(2 43716 5); (iii) φ 2 (7461325) = 5724361 and (f, l)(7 461325) = (0, 4) = (L -1, F -1)(5 72436 1).

It follows from (5.6)-(5.9) that the product φ 1 • φ 2 : A 2n-1 → Alt 2n-1 has the property that for every σ from A 2n-1 we have: (f -1, l -1)(φ 1 • φ 2 )(σ) = (L -1, F -1)φ 2 (σ) = (f, l)σ. In view of (5.3) and since grn = max(l, f), this implies the identity:

(5.10) g n (k) = # A2n-1,k-1 = # Alt 2n-1,k .

For n ≥ 1 each set Alt 2n-1,k can be split into two subsets of the same cardinality Alt < 2n-1,k + Alt > 2n-1,k , depending on whether the greater neighbor k is on the left, or on the right of (2n + 1). Now, with each permutation σ = x 1 x 2 • • • x j-2 k (2n -1)x j+1 x j+2 • • • x 2n-1 from Alt < 2n-1,k associate the permutation

φ 3 (σ) := k x ′ j-2 • • • x ′ 2 x ′ 1 (2n) x ′ 2n-1 • • • x ′ j+2 x ′ j+1 (k + 1)
, where

x ′ j = x j , if x j ≤ k; x j + 1, if x j > k.
It is obvious that φ 3 is a bijection of Alt 2n-1,k onto the set E 2n,k of all permutations τ from Alt 2n such that F τ = k, L τ = k + 1. As #E 2n,k = E 2n (k, k + 1), it follows that (5.11) # Alt 2n-1,k = 2# Alt < 2n-1,k = 2E 2n (k, k + 1).

This proves identity (5.2) in view of (5.10) and (5.11).

Final Remarks. The Seidel Matrix method developed in this paper can also be used to derive the three-variable generating functions obtained in our previous two papers [START_REF] Foata | Tree Calculus for Bivariate Difference Equations[END_REF] and [START_REF] Foata | Secant Tree Calculus, to appear in Central Europ[END_REF]. It is also the main tool in our next paper [START_REF] Foata | Three-variable generating function for Poupard-Entringer Matrices[END_REF].

  Fig. 1.1. The Poupard Numbers g n (k). k = 1 2 3 4 5 6 7 Sum n = 1 1 1 2 1 3 1 5 3 5 15 21 15 5 61 4 61 183 285 327 285 183 61 1385 Fig. 1.2. The Poupard Numbers h n (k).

  Now, let the sequence of matrices (W n ) = (e n (m, k)) be obtained from the matrices (M n ) = (E n (m, k)) by making the following modifications: (W1) W 1 := (0); (W2) W n := M n for n ≡ 2, 3 (mod 4) and n ≥ 2; (W3) W n := (-1)M n for n ≡ 0, 1 (mod 4); (W4) delete the lower triangle from each matrix W n ; (W5) make the labels start from 0, 1, 2, . . . In other words, for m < k define the normalized Bi-Entringer Numbers e n (m, k) to be: e 2n (m, k) := (-1) n+1 E 2n (m + 1, k + 1); (3.9) e 2n+1 (m, k) := (-1) n+1 E 2n+1 (m + 1, k + 1). (3.10) Their first values appear in Fig. 3.1.

Fig. 3

 3 Fig. 3.1. The normalized Bi-Entringer Numbers e n (m, k).

  )e -tr dr, so that identity (1.3) is proved.

  .3.

	m =	1	2 3 4 5	6	Sum
	n = 1	1			1
	2	1			1
	3	1	1		2
	4	2	2 1		5
	5	5	5 4 2		16
	6	16 16 14 10 5		61
	7	61 61 56 46 32 16	272

Fig. 1.3. The Entringer Numbers E n (m).


Dominique Foata

Guo-Niu Han

Secant Tree Calculus

Keywords: Tree Calculus, partial difference equations, binary increasing labeled trees, secant and tangent trees, end of minimal chain, parent of maximum leaf, bivariate distributions, secant numbers, Entringer distribution, alternating permutations. Mathematics Subject Classifications. 05A15, 05A30, 11B68

A true Tree Calculus is being developed to make a joint study of the two statistics "eoc" (end of minimal chain) and "pom" (parent of maximum leaf) on the set of secant trees. Their joint distribution restricted to the set {eoc -pom ≤ 1} is shown to satisfy two partial difference equation systems, to be symmetric and to be expressed in the form of an explicit three-variable generating function.

Introduction

Recently, a revival of studies on arithmetical and combinatorial properties of both tangent and secant numbers has taken place, using Désiré André's old model of alternating permutations [An1979, An1881], or the equivalent structure of binary increasing labeled trees, called tangent and secant trees. See, e.g., the papers [GHZ10, Pr08, Pr00, Fu00, HRZ01, Jos10, SZ10, KR12, FH12], or the memoir [START_REF] Stanley | A Survey of Alternating Permutations[END_REF] and our studies on the doubloon model [START_REF] Foata | The doubloon polynomial triangle[END_REF][START_REF] Foata | Doubloons and q-secant numbers[END_REF][START_REF] Foata | Doubloons and new q-tangent numbers[END_REF]. Recall that the secant numbers, denoted by E 2n , appear in the Taylor expansions of sec u: The study of the secant numbers E 2n (n ≥ 0) developed in the present paper makes use of the combinatorial model of binary increasing labeled trees (T 2n ) (n ≥ 0) with an even number of nodes, also called secant trees, as #T 2n = E 2n . Their definitions are recalled in Section 2; just note that in such a tree each node has no child (it is then called a leaf), or two children, except the rightmost one that has one left child only. See, e.g., the whole set T 4 displayed in Fig. 1.1.

sec u = 1 cos u = n≥0 u 2n (
The refinement of each secant number E 2n , we are concerned with, takes the form of a double sum E 2n = m,k f 2n (m, k) of positive integers, where each summand f 2n (m, k) is defined by means of two statistics "eoc" ("end of minimal chain") and "pom" ("parent of maximum leaf"), whose domain is T 2n , in the following manner:

(1.2) f 2n (m, k) := #{t ∈ T 2n : eoc(t) = m and pom(t) = k}.

The end-of-minimal-chain eoc(t) of a tree t is defined to be the label of the leaf that is reached, when, starting with the tree root, one gets along a chain of nodes, always going from parent to the smaller child, if any. The parent-of-maximum-leaf pom(t) of t from T 2n is simply defined to be the label of the father of leaf 2n. Again, check Fig. 1.1 where the values of "eoc" and "pom" are given for all trees from T 4 .

3 4

1 2 ❅ ❅✟ ✟ ✟ ❅ ❅ 4 1 3 2 eoc = pom = 3 1 4 3 1 2 ❅ ❅✟ ✟ ✟ ❅ ❅ 3 1 4 2 4 2 2 4 1 3 ◗ ◗ ◗ ◗ ◗ ✟ ✟ 4 2 3 1 3 2 2 3 1 4 ◗ ◗ ◗ ◗ ◗ ✟ ✟ 3 2 4 1 2 3 4 2 1 3 ❅ ❅✟ ✟ ✟ ❅ ❅ 2 1 4 3 3 2 Fig. 1.1
Those two statistics have been introduced by Poupard [Po89] on tangent trees (n odd). She proved that "eoc" and "1+pom" were equidistributed on each set T 2n+1 of tangent trees, also that their common univariable distribution satisfied a difference equation system; she further calculated their generating function. In [START_REF] Foata | Tree Calculus for Bivariable Difference Equations[END_REF] it was proved that the equidistribution actually holds on every set T n (n ≥ 1) of tangent and secant trees by constructing an explict bijection φ of T n onto itself with the property that: 1+pom(t) = eoc φ(t) for all t.

The purpose of this paper is then to calculate the joint distribution of "eoc" and "pom" on each T 2n and in particular derive an explicit threevariable exponential generating function (Theorem 1.5). To achieve this we prove that the coefficients f 2n (m, k) are solutions of two partial difference equation systems. The proof is based on an original true Tree Calculus, which consists of partitioning each set of secant trees into smaller subsets and developing a natural algebra on those subsets (Sections 3, 4 and 5).

Note that the ranges of "eoc" and "pom" on T 2n are the intervals [2, 2n] and [1, 2n -1], respectively. The first values of the matrices

M 2n := (f 2n (m, k)) (2 ≤ m ≤ 2n; 1 ≤ k ≤ 2n -1) are listed in Table 1.2. For each matrix have been evaluated the row sums f 2n (m, •) := k f 2n (m, k) = #{t ∈ T 2n : eoc(t) = m} (resp. column sums f 2n (•, k) := m f 2n (m, k) = #{t ∈ T 2n : pom(t) = k})
on the rightmost column (resp. the bottom row). In the South-East-corner is written the total sum

(1.3) f 2n (•, •) = m,k f 2n (m, k) = E 2n .
As "1+pom" and "eoc" are equidistributed, we have: On each entry f 2n (m, k) may be defined two partial differences with respect to m and k as follows:

(1.4) f 2n (•, k -1) = f 2n (k, •) (2 ≤ k ≤ 2n). M 2 = k = 1 f 2 (m, .) m = 2 1 1 f 2 (., k) 1 E 2 = 1 M 4 = k = 1 2 3 f 4 (m, .) m = 2 . . 1 1 3 1 2 . 3 4 . 1 . 1 f 4 (., k) 1 3 1 E 4 = 5 M 6 = k = 1 2 3 4 5 f 6 (m, .) m = 2 . .
∆ m f 2n (m, k) := f 2n (m + 1, k) -f 2n (m, k); (1.5) ∆ k f 2n (m, k) := f 2n (m, k + 1) -f 2n (m, k). (1.6) By convention f 2n (m, k) := 0 if (m, k) ∈ [2, 2n] × [1, 2n -1].
Our main results are the following.

Theorem 1.1. The finite difference equation systems hold:

∆ m 2 f 2n (m, k) + 4 f 2n-2 (m, k -2) = 0 (2 ≤ m ≤ k -3 < k ≤ 2n -1); (R 1) ∆ k 2 f 2n (m, k) + 4 f 2n-2 (m, k) = 0 (2 ≤ m ≤ k -1 < k ≤ 2n -3). (R 2)
The first two top rows and rightmost two columns of the upper triangles

{f 2n (m, k) : 2 ≤ m < k ≤ 2n -1} (n ≥ 2) can be evaluated in function of the row or column sums f 2n-2 (•, k), f 2n-2 (m, •), as is now stated. Theorem 1.2. We have: (1.7) f 2n (2, k) = f 2n-2 (•, k -2) = f 2n-2 (k -1, •) (3 ≤ k ≤ 2n -1); [First top row] f 2n (3, k) = 3 f 2n (2, k) (4 ≤ k ≤ 2n -1); [Second top row] f 2n (m, 2n -1) = f 2n-2 (m, •) = f 2n-2 (•, m -1) (2 ≤ m ≤ 2n -2); [Rightmost column] f 2n (m, 2n -2) = 3 f 2n (m, 2n -1) (2 ≤ m ≤ 2n -3).
[Next to rightmost column] Proposition 1.3. We further have:

f 2 (•, 1) = 1; f 2n (•, 1) = f 2n-2 (•, •) = E 2n-2 (n ≥ 2); (1.8) f 2n (•, 2) = 3f 2n-2 (•, •) = 3E 2n-2 (n ≥ 2); (1.9) ∆ m 2 f 2n (m, •) + 4 f 2n-2 (m, •) = 0 (2 ≤ m ≤ 2n -2); (R 3) ∆ k 2 f 2n (•, k) + 4 f 2n-2 (•, k) = 0 (1 ≤ k ≤ 2n -3). (R 4)
Theorem 1.4. The previous two theorems and Proposition 1.3 provide an explicit algorithm for calculating the entries of the upper triangles of the matrices M 2n = (f 2n (m, k)) (n ≥ 1).

The entries of the lower triangles {f 2n (m, k) : 1 ≤ k < m ≤ 2n} in Tables 1.1 have been calculated directly by means of formula (1.2). Contrary to the upper triangles we do not have any explicit numerical algorithm to get them; only the entries situated on the three sides of those lower triangles can be directly evaluated, as shown in Section 6. See, in particular, Table 6.1. For the upper triangles, we can derive an explicit generating function, as stated in the next theorem.

Theorem 1.5. The triple exponential generating function for the upper triangles of the matrices (f 2n (m, k)) is given by

(1.10) 2≤m<k≤2n-1 f 2n (m, k) x 2n-k-1 (2n -k -1)! y k-m-1 (k -m -1)! z m-2 (m -2)! = cos(2y) + 2 cos(2(x -z)) -cos(2(z + x)) 2 cos 3 (x + y + z) .
The right-hand side of (1.10) is symmetric in x, z. Hence, the change x ↔ z in the left-hand side of (1.10) shows that (1.11)

f 2n (2n + 1 -k, 2n + 1 -m) = f 2n (m, k).
The upper triangles already mentioned are then symmetric with respect to their counter-diagonals. This result can also be extended as follows.

Theorem 1.6. Let Up(2n) be the set of all

(m, k) from [2, 2n]×[1, 2n-1] such that either m -1 ≤ k, (m, k) = (3, 1), or (m, k) = (2n, 2n -2).
Then (1.11) holds for every (m, k) ∈ Up(2n).

Those theorems and proposition are proved in the next sections, once the main ingredients on Tree Calculus have been developed.

Tree Calculus

We use the traditional vocabulary on trees, such as node, leaf, child, root, . . . When a node is not a leaf, it is called an internal node.

Definition. For each positive integer n a secant tree of size 2n, that is, an element of T 2n , is defined by the following axioms:

(1) it is a labeled tree with 2n nodes, labeled 1, 2, . . . , 2n; the node labeled 1 being the root;

(2) each node has no child (then called a leaf ), or one child, or two children;

(3) the label of each node is smaller than the label of its children, if any;

(4) the tree is planar and each child of each node is, either on the left (it is then called the left child ), or on the right (the right child ); moreover, the tree can be embedded on the Euclidean plane as follows: the root has coordinates (0, 0), the left child (if any) (-1, 1), the right child (if any) (1, 1), the grandchildren (if any) (-3/2, 2), (-1/2, 2), (1/2, 2), (3/2, 2), the greatgrandchildren (if any) (-7/4, 3), (-5/4, 3), . . . , (7/4, 3), etc. With this convention all the nodes have different abscissas. The node having the maximum abscissa is then defined in a unique manner. Call it the rightmost node.

(5) every node is, either a leaf, or a node with two children, except the rightmost node, which has one left child, but no right child. This rightmost node will then be referred to as being the one-child node.

The orthogonal projections of the 2n nodes of a secant tree t from T 2n onto a horizontal axis yields a permutation σ = σ(1)σ(2) • • • σ(2n) of 12 • • • 2n having the property that x 1 > x 2 , x 2 < x 3 , x 3 > x 4 , . . . , in an alternating way, usually named alternating (see [START_REF] Xavier | Séries génératrices énumératives[END_REF], [START_REF] Kuznetsov | Increasing trees and alternating permutations[END_REF], [St99]). The corresponding alternating permutation has been indicated for each t ∈ T 4 in Fig. 1.1

Let t ∈ T 2n (n ≥ 1). If a node labeled a has two children labeled b and c, define min a := min{b, c}; if it has one child b, let min a := b. The minimal chain of t is defined to be the sequence

a 1 → a 2 → a 3 → • • • → a j-1 → a j ,
with the following properties: (i) a 1 = 1 is the label of the root; (ii) for i = 1, 2, . . . , j-2 the (i+1)-st term a i+1 is the label of an internal node and a i+1 = min a i ; (iii) a j is the node of a leaf. Define the "end of the minimal chain" of t to be eoc(t) := a j . If the leaf with the maximum label 2n is incident to a node labeled k, define its "parent of the maximum leaf" to be pom(t) := k. See Fig. 1.1.

We adopt the following notations and conventions: for each triple (n, m, k) let T 2n,m,k (resp. T 2n,m,• , resp. T 2n,•,k ) denote the subset of T 2n of all trees t such that eoc(t) = m and pom(t) = k (resp. eoc(t) = m, resp. pom(t) = k). Also, symbols representing families of trees will also designate their cardinalities. With this convention T n,m,k := #T n,m,k . The matrix of the upper triangles T 2n,m,k (2 ≤ m < k ≤ 2n -1) will be denoted by Upper(T 2n ).

Subtrees (possibly empty) are indicated by the symbols " ," "▽", or " ." The notation " ❅ ❅ " (resp. " \ ," resp. "▽ \ ") is used to indicate that the subtree " " (resp. " ," resp. "▽") contains the one-child node or is empty. Letters occurring below or next to subtrees are labels of their roots. The end of the minimal chain in each tree is represented by a bullet "•."

In the sequel certain families of secant trees will be represented by symbols, called trunks. For example, the symbol

A = ❅ ❅ • m b
is the trunk that designates the family of all trees t from the underlying set T 2n having a node b, parent of both a subtree " " and the leaf m, which is also the end of the minimal chain. Notice that unlike the secant trees which are ordered, the trunk is unordered, so that (2.1)

❅ ❅ • m b ≡ ❅ ❅ b • m .
When the subtree " " contains the one-child node or is empty, we let

A( ❅ ❅ ) := ❅ ❅ • m b ❅ ❅ ≡ ❅ ❅ ❅ ❅ b • m
, be the family of all trees t from the underlying set T 2n having a node b, parent of the right child " ❅ ❅ " and the left child leaf m. Let A(⋆) be the set of all trees from A such that " " is not empty and does not contain the one-child node. We have the following decomposition (2.2)

A = A(⋆) + A( ❅ ❅ ).
When a further condition (C) is imposed on a trunk A we shall use the notation [A, (C)]. For example, the symbol

B = [ ❅ ❅ • m b , a ]
is the trunk that has the same characteristic of the trunk A as above with the further property that the node labeled a belongs, neither to the subtree of root b, nor to the path going from root 1 to b.

In our Tree Calculus we shall mostly compare the cardinalities of certain pairs of trunks, as shown in the following two examples.

Example 1. The two trunks [ ❅ ❅ m+1 m+2 • , m] and [ ❅ ❅ m m+1 • , m + 2]
have the same cardinalities, by using the bijection m m+1 m+2 m+2 m m+1 . Example 2. To compare the cardinalities of the following two trunks

C = ❅ ❅ ❅ ❅ ❅ k+2 2n k+1 ▽ k and D = ❅ ❅ ❅ ❅ ❅ k+2 k+1 2n ▽ k ,
we decompose them according to the location of the one-child node:

C = ❅ ❅ ❅ ❅ ❅ k+2 2n k+1 ▽ k + ❅ ❅ ❅ ❅ ❅ k+2 2n k+1 ▽ \ k + ❅ ❅ ❅ ❅ ❅ ❅ ❅ k+2 2n k+1 ▽ k + ❅ ❅ ❅ ❅ ❅ \ k+2 2n k+1 ▽ k := C(⋆) + C(▽ \ ) + C( ❅ ❅ ) + C( \ ); D = ❅ ❅ ❅ ❅ ❅ k+2 k+1 2n ▽ k + ❅ ❅ ❅ ❅ ❅ k+2 k+1 2n ▽ \ k + ❅ ❅ ❅ ❅ ❅ ❅ ❅ k+2 k+1 2n ▽ k := D(⋆) + D(▽ \ ) + D( ❅ ❅ ).
In the above seven trunks of the two decompositions the symbols " ," "▽," " " without slash are not empty and do not contain the one-child node. Furthermore, note that D = D(⋆) + D(▽ \ ) + D( \ ) also holds.

Pivoting the two subtrees on each of the nodes k, (k +1), (k +2) in C(⋆) (resp. in D(⋆)) yields the same trunk, as in (2.1). We then say that subtree pivoting is permitted on those nodes. Furthermore, the three subtrees " ," " " and "▽" in C(⋆) play a symmetric role, while in D(⋆) only " " and "▽," on the one hand, and " " and "▽," on the other hand, have a symmetric role. Hence,

C(⋆) = 2 D(⋆).
Now, remember that in each secant tree the one-child node lies at the rightmost position. This implies that subtree pivoting on each of the ancestors of the one-child is not permitted. Thus, subtree pivoting in C(▽ \ ) and D(▽ \ ) is only permitted on nodes k + 2 and k + 1. On the other hand, the two subtrees " " and "' " play a symmetric role in C(▽ \ ), but not in D(▽ \ ). Hence,

C(▽ \ ) = 2 D(▽ \ ).
In C( ❅ ❅ ) and D( ❅ ❅ ) the two subtrees " " and "▽" play a symmetric role. Moreover, subtree pivoting on nodes

k + 2 is permitted in C( ❅ ❅ ), but not in D( ❅ ❅ ). Hence, C( ❅ ❅ ) = 2 D( ❅ ❅ ), so that C -2 D = C( \ ).
3. Proof that (R 1) holds The decomposition

T 2n,m,k = ❅ ❅ m m+1 • + [ ❅ ❅ m • , m + 1]
means that in each tree from T 2n,m,k the node (m + 1) is, or is not, the sibling of the leaf m. In the next decomposition the node m is, or is not, the parent of the leaf (m + 1):

T 2n,m+1,k = ❅ ❅ m+1 m • + [ ❅ ❅ m+1 • , m].
As already explained in Example 1, Section 2, we can write:

∆ m T 2n,m,k = T 2n,m+1,k -T 2n,m,k = ❅ ❅ m+1 m • - ❅ ❅ m m+1 • , so that ∆ m 2 T 2n,m,k = (T 2n,m+2,k -T 2n,m+1,k ) -(T 2n,m+1,k -T 2n,m,k ) = ❅ ❅ m+2 m+1 • - ❅ ❅ m+1 m+2 • - ❅ ❅ m+1 m • + ❅ ❅ m m+1 • := A - B - C + D .
Depending on the mutual positions of nodes m, (m + 1) and (m + 2) the further decompositions prevail, as again k still remains attached to (2n):

A = ❅ ❅ ❅ • m+1 m+2 m + [ ❅ ❅ ❅ • m+1 m+2 , m] := A 1 + A 2 ; B = ❅ ❅ m+1 m • m+2 + [ ❅ ❅ m+1 m+2 • , m] := B 1 + B 2 ; C = ❅ ❅ m+1 m • m+2 + ❅ ❅ ❅ • m m+1 m+2 + [ ❅ ❅ ❅ • m m+1 , m + 2] := C 1 + C 2 + C 3 ; D = ❅ ❅ ❅ ❅ m+2 • m m+1 + [ ❅ ❅ m m+1 • , m + 2] := D 1 + D 2 .
In the above decompositions the subsets B 1 and C 1 are identical. Furthermore,

A 2 = C 3 and B 2 = D 2 . Accordingly, ∆ m 2 T 2n+1,m,k = A 1 -2 B 1 -C 2 +D 1 .
A further decomposition of those four terms, depending upon the occurrence of the one-child node, is to be worked out:

A 1 := A 1 (⋆) + A 1 ( ❅ ❅ ) + A 1 ( \ ); B 1 := B 1 (⋆) + B 1 ( \ ); C 2 := C 2 (⋆) + C 2 ( ❅ ❅ ) + C 2 ( \ ); D 1 := D 1 (⋆) + D 1 ( ❅ ❅ ) + D 1 ( \ ). Now, B 1 (⋆) can be decomposed into B 1 (⋆) = ❅ ❅ m+1 m • m+2 = ❅ ❅ m+1 m • m+2 + ❅ ❅ ❅ ❅ • m+1 m+2 m = B 1,1 (⋆) + B 1,2 (⋆),
where " " and " " are supposed to be non-empty in B 1,2 (⋆). By the Tree Calculus techniques developed in Section 2, we have A 1 (⋆) = 2 B 1,2 (⋆). On the other hand, B 1 ( \ ) can also be written

B 1 ( \ ) = ❅ ❅ ❅ ❅ • \ m+1 m+2 m , so that A 1 ( ❅ ❅ ) = 2 B 1 ( \ ) and A 1 ( \ ) = B 1 ( \ ). Furthermore, C 2 (⋆) = D 1 (⋆), C 2 ( ❅ ❅ ) = 2 D 1 ( ❅ ❅ ) and C 2 ( \ ) = D 1 ( \ ). Altogether, A 1 - 2 B 1 -C 2 + D 1 = A 1 (⋆) + A 1 ( ❅ ❅ ) + A 1 ( \ ) -2 B 1,1 (⋆) + B 1,2 (⋆) + B 1 ( \ ) -C 2 (⋆) + C 2 ( ❅ ❅ ) + C 2 ( \ ) + D 1 (⋆) + D 1 ( ❅ ❅ ) + D 1 ( \ ) = A 1 ( \ ) -2 B 1,1 (⋆) -D 1 ( ❅ ❅ ).
As m is supposed to be at least equal to 2, we can write

A 1 ( \ ) = ❅ ❅ ❅ ❅ ❅ •m+2 m+1 \ m ▽ , D 1 ( ❅ ❅ ) = ❅ ❅ ❅ ❅ ❅ ❅ m • ❅ ❅ m+1 m+2 ▽
, which shows that those two families are equal. Thus,

∆ m 2 T 2n,m,k = -2 B 1,1 (⋆) = -2 ❅ ❅ m+1 m • m+2 .
This expression is also equal to -4 T 2n-2,m,k-2 , because in each tree t from B 1 the nodes (m + 1) and (m + 2) are both leaves. Remove them, as well as the two edges going out of m, and subtract 2 from all the remaining nodes greater than (m + 2). The tree thereby derived belongs to T 2n-2,m,k-2 .

Tree Calculus for proving that (R 2) holds

With n ≥ 3 and 2 ≤ m ≤ k -1 < k ≤ 2n -3 we have:

T 2n,m,k = [ ❅ ❅ k+1 2n k , m] + [ ❅ ❅ 2n k , m, k + 1],
meaning that each tree from T 2n,m,k has one of the two forms: either k + 1 is incident to k, or not, and the leaf m is the end of the minimal chain.

Using the same dichotomy,

T 2n,m,k+1 = [ ❅ ❅ ❅ k+1 2n k , m] + [ ❅ ❅ 2n k+1 , m, k].
As the second terms of the above two equations are in one-to-one correspondence by the transposition (k, k + 1) we have:

T 2n,m,k+1 -T 2n,m,k = [ ❅ ❅ ❅ k+1 2n k , m] -[ ❅ ❅ k+1 2n k , m] := B -A.
In the same manner,

T 2n,m,k+2 -T 2n,m,k+1 = [ ❅ ❅ ❅ k+2 2n k+1 , m] -[ ❅ ❅ k+2 2n k+1 , m] := D -C. ∆ k 2 T 2n,m,k = T 2n,m,k+2 -T 2n,m,k+1 -T 2n,m,k+1 -T 2n,m,k Thus, = D -C -B + A.
The further decompositions of the components of the previous sum depend on the mutual positions of the nodes k, (k + 1), (k + 2);

D = [ ❅ ❅ ❅ k+2 2n k+1 , m] = [ ❅ ❅ ❅ k+2 2n k+1 , m, k ] + [ ❅ ❅ ❅ ❅ ❅ k+2 2n k+1 ▽ k , m] := D 1 + D 2 ; C = [ ❅ ❅ k+2 2n k+1 , m] = [ ❅ ❅ k+2 2n k+1 , m, k ] + [ ❅ ❅ ❅ k+1 k+2 2n k , m] := C 1 + C 2 ; B = [ ❅ ❅ ❅ k+1 2n k , m] = [ ❅ ❅ ❅ k+1 2n k , m, k + 2] + [ ❅ ❅ ❅ k+1 k+2 2n k , m] + [ ❅ ❅ ❅ ❅ ❅ k+2 k+1 2n ▽ k , m] + [ ❅ ❅ ❅ k+1 2n k k+2 , m] + [ ❅ ❅ ❅ ❅ ❅ ▽ k+2 k+1 2n k , m] := B 1 + B 2 + B 3 + B 4 + B 5 ; A = [ ❅ ❅ k+1 2n k , m] = [ ❅ ❅ k+1 2n k , m, k + 2 ] + [ ❅ ❅ ❅ k+1 k+2 k 2n , m] := A 1 + A 2 ,
where " " and " " cannot be both empty in B 3 and B 5 .

Obviously, (1) With the same notation as in (2.2) write:

D 1 = B 1 and C 1 = A 1 , so that the sum D -C -B + A may be written (B 2 -B 4 ) -(C 2 -A 2 ) + (D 2 -B 3 -B 5 ) -2 B 2 ,
B 2 = B 2 (⋆) + B 2 ( ❅ ❅ ) and B 4 = B 4 (⋆) + B 4 ( ❅ ❅ ). First, B 2 (⋆) = B 4 (⋆), but B 2 ( ❅ ❅ ) = 2 B 4 ( ❅ ❅ ). Hence, B 2 -B 4 = B 4 ( ❅ ❅ ) = [ ❅ ❅ ❅ ❅ ❅ ❅ 2n k+2 k+1 k , m]. (2) Next, C 2 = C 2 (⋆) + C 2 ( ❅ ❅ ) + C 2 ( \ ) and A 2 = A 2 (⋆) + A 2 ( ❅ ❅ ) + A 2 ( \ ). As before, C 2 (⋆) = A 2 (⋆) and also C 2 ( \ ) = A 2 ( \ ). However, C 2 ( ❅ ❅ ) = 2 A 2 ( ❅ ❅ ). Altogether, C 2 -A 2 = A 2 ( ❅ ❅ ) = [ ❅ ❅ ❅ ❅ ❅ ❅ 2n k+1 k k+2 , m].
(3) The calculation of the third sum requires the following decompositions:

D 2 := D 2 (⋆) + D 2 (▽ \ ) + D 2 ( ❅ ❅ ) + D 2 ( \ ); B 3 := B 3 (⋆) + B 3 (▽ \ ) + B 3 ( ❅ ❅ ); B 5 := B 5 (⋆) + B 5 (▽ \ ) + B 5 ( ❅ ❅ );
12 By the Tree Calculus techniques developed in Section 2, especially Example 2, we have

D 2 (⋆) = 2 B 3 (⋆) = 2 B 5 (⋆); D 2 (▽ \ ) = 2 B 3 (▽ \ ) = 2 B 3 (▽ \ ); D 2 ( ❅ ❅ ) = 2 B 3 ( ❅ ❅ ) = 2 B 3 ( ❅ ❅ ).
Hence,

D 2 -B 3 -B 5 = D 2 ( \ ) = [ ❅ ❅ ❅ ❅ ❅ ❅ ▽ k \ k+1 k+2 2n , m]. Now A 2 ( ❅ ❅ ) = [ ❅ ❅ ❅ ❅ ❅ ❅ 2n k+1 k k+2 , m] = [ ❅ ❅ ❅ ❅ ❅ ❅ 2n k+1 k k+2 , m] + [ ❅ ❅ ❅ ❅ ❅ 2n ❅ ❅ k+1 k k+2 ▽ , m],
where the two subtrees " " and "▽" are non-empty. The last identity can be rewritten:

A 2 ( ❅ ❅ ) = B 4 ( ❅ ❅ ) + D 2 ( \ ). Hence, ∆ k 2 T 2n,m,k = D - C -B + A = (B 2 -B 4 ) -(C 2 -A 2 ) + (D 2 -B 3 -B 5 ) -2 B 2 = B 4 ( ❅ ❅ ) -A 2 ( ❅ ❅ ) + D 2 ( \ ) -2 B 2 = -2 B 2 = -2 [ ❅ ❅ ❅ k+1 k+2 2n
k , m]. The last term is also equal to -4 T 2n-2,m,k , because in each tree t from B 2 the nodes (k + 2) and (2n) are both leaves. Remove them, as well as the two edges going out of (k + 1), change (k + 1) into (2n -2) and subtract 2 from all the remaining nodes greater than (k + 2). The tree thereby derived belongs to T 2n-2,m,k .

Proofs of Theorem 1.2, Proposition 1.3 and Theorem 1.4

Proof of Theorem 1.2. First top row. The trees t from T 2n such that eoc(t) = 2 contain the edge 2 → 1. Remove it and change each remaining node label j by j -2. We get a tree t ′ from T 2n-2 such that pom(t ′ ) = k -2. The second equality is a consequence of (1.4).

Second top row.

As k ≥ 4, the subtrees " " and " " below are nonempty, so that

f 2n (3, k) = ❅ ❅ ❅ 1 3 2 • = ❅ ❅ ❅ 1 3 2 • ❅ ❅ + ❅ ❅ ❅ ❅ 1 3 2 • \ := A = A( ❅ ❅ ) + A( \ ); f 2n (2, k) = ❅ ❅ ❅ ❅ 1 3 2 • := B = ❅ ❅ ❅ ❅ 1 3 2 • ❅ ❅ = B( ❅ ❅ ), since B(⋆) is empty. Therefore, A( ❅ ❅ ) = 2 B( ❅ ❅ ), A( \ ) = B( ❅ ❅ ) and then f 2,n (3, k) = 3 f 2n (2, k).
Rightmost column. The trees t from T 2n such that eoc(t) = m and pom(t) = 2n -1 contain the rightmost path 2n → (2n -1) → . Remove it. What is left is a tree t ′ from T 2n-2 such that eoc(t ′ ) = m. The second equality is a consequence of (1.4).

Next to rightmost column. If t ∈ T 2n and pom(t) = 2n -1, then t contains the rightmost path 2n → (2n -1) →, as already noted. On the other hand, the node with label (2n -2) is necessarily a leaf. The transposition (2n -2, 2n -1) transforms t into a tree t 1 such that pom(t 1 ) = 2n -2. Also, removing the path 2n → (2n -1) and rooting either the subtree 2n-1 տր 2n , or the subtree 2n տր 2n-1 , onto the leaf labeled (2n -2) gives rise to two trees t 2 , t 3 such that pom(t 2 ) = pom(t 3 ) = 2n -2.

Proof of Proposition 1.3. For (1.8) and (1.9) we only have to reproduce the proofs made in Theorem 1.2 for the first and second top rows, the parent of the maximum node playing no role.

To obtain (R 4) simply write (R 2) for m = 2 and rewrite it using the first identity of Theorem 1.2 dealing with the "first top row." Next, (R 3) is deduced from (R 4) by using identity (1.4).

Proof of Theorem 1.4. By induction, the row and column sums f 2n (m, •) and f 2n (•, k) of the matrices M 2n can be calculated by means of relations (1.8), (1.9) and, either (R 3), or (R 4). The first and second top rows (resp. rightmost and next to rightmost columns) of the matrix M 2n are known by Theorem 1.2. It then suffices to apply, either rule (R 1), from top to bottom, or rule (R 2) from right to left to obtain the remaining entries of the upper triangles of M 2n .

The lower triangles

Observe that for 2n ≥ 6 the non-zero entries of the first row, first column and last column of M 2n are identical and they differ from the entries in the bottom row. For instance, the sequence 5, 15, 21, 15, 5 in M 8 appears three times, but the bottom row reads: 16, 16, 14, 10, 5.

By Theorem 1.2 we already know that

f 2n (2, k) = f 2n-2 (k -1, •) = f 2n (k-1, 2n-1) (3 ≤ k ≤ 2n-1). We also have: f 2n (m, 1) = f 2n-2 (m-1, •) (3 ≤ m ≤ 2n -1)
, by using this argument: each tree t from T 2n satisfying pom(t) = 1 has its leaf node 2n incident to root 1. Just remove the edge 2n → 1. Change each remaining label j to j -1. We get a secant tree t ′ belonging to T 2n-2 . The mapping t → t ′ is bijective; moreover, eoc(t ′ ) = eoc(t) -1. As a summary, (6.1)

f 2n (2, k) = f 2n (k -1, 2n -1) = f 2n (k, 1) (3 ≤ k ≤ 2n -1).
Introduce a further statistic "ent" (short hand for "Entringer") on each tree t from T n (even for tangent trees) as follows: ent(t) is the label of the rightmost node of t. The distribution of "ent" is well-known, mostly associated with the model of the alternating permutations and traditionally called Entringer distribution (see, e.g., [START_REF] Entringer | A combinatorial interpretation of the Euler and Bernoulli numbers[END_REF], [START_REF] Poupard | De nouvelles significations énumératives des nombres d'Entringer[END_REF], [Po87], [START_REF] Gelineau | Bijections for Entringer families[END_REF]). We also know how to calculate the generating function of that distribution and build up the Entringer triangle (Ent n (j)) (1 ≤ j ≤ n -1; n ≥ 2), as done in Table 6.1.

For instance, the leftmost 61 on the row n = 7 is the sum of all the entries in the previous row (including an entry 0 on the right!); the second 61 is the sum of the leftmost five entries; 56, the sum of the leftmost four entries; 46, the sum of the leftmost three entries; 32, the sum of the leftmost two entries and 16 is equal to the leftmost entry. Let Ent n (j) = #{t ∈ T n : ent(t) = j}. j = 1 2 3 4 5 6 n = 2 1 3 1 1 4 2 2 1 5 5 5 4 2 6 16 16 14 10 5 7 61 61 56 46 32 16 Table 6.1. The Entringer distribution Proposition 6.1. For 2 ≤ k ≤ 2n -2 we have:

(6.2) f 2n (2n, k) = Ent 2n-2 (k -1).
Proof. Note that in a tree t ∈ T 2n such that eoc(t) = 2n and pom(t) = k the leaf labeled 2n is the unique son of the node labeled k, which is also the rightmost node. Let (1 = a 1 ) → a 2 → a 3 → • • • → (a j-1 = k) → (a j = 2n) be the minimal chain of t. Form a new tree t ′ by means of the following changes: (i) delete the path → a j-1 → 2n; (ii) for i = 1, 2, . . . , j -2 replace each node label a i of the minimal chain by a i+1 -1;

(iii) replace each other node label b by b -1. The label of the rightmost node of t ′ is then equal to the pom(t)-1 = k-1. The mapping t → t ′ is obvious bijective.

Finally, the upper diagonal {f 2n (k + 1, k) : (1 ≤ k ≤ 2n -1)} of the lower triangle in each matrix M 2n can also be fully evaluated. First, in an obvious manner, (6.3)

f 2n (2, 1) = f 2n (2n, 2n -1) = 0.
Second, the identities

(6.4) f 2n (3, 2) = 2 f 2n (3, 1) = f 2n (2n -1, 2n -2) = 2 f 2n (2n, 2n -2)
(also equal to f 2n-4 (•, •) = E 2n-4 ) can be proved as follows. To each tree t ∈ T 2n such that eoc(t) = 3, pom(t) = 1 there correspond two trees, whose "eoc" and "pom" are equal to 2 and 3, respectively, as illustrated by the diagram:

f 2n (3, 1) = ❅ ❅ ❅ ❅ 1 3 2n 2 • → ❅ ❅ ❅ 1 2n 3 2 • = f 2n (3, 2).
Likewise, each tree t ∈ T 2n such that eoc(t) = 2n and pom(t) = 2n -2 necessarily has its rightmost four nodes equal to (2n -1), b, 2n, (2n -2) in that order, with b being a node less than (2n -2). In particular, the latter node is its rightmost (one-child) node. To such a tree there correspond two trees, whose "eoc" and "pom" are equal to (2n -1), (2n -2), respectively, as illustrated by the next diagram. In particular, the node b becomes the rightmost node of those two such trees.

❅ ❅ ❅ ❅ 2n-1 2n b • 2n-2 → ❅ ❅ ❅ 2n-2 2n-1 b • 2n
. Proposition 6.2. We have the crossing equalities:

(6.5) f 2n (k -1, k) + f 2n (k + 1, k) = f 2n (k, k -1) + f 2n (k, k + 1), for 3 ≤ k ≤ 2n -2.
The involved entries are located on the four bullets drawn in the following diagramme.

k -1 k k + 1 • • • • k -1 k k + 1
Proof. Let i, j be two different integers from the set {(k-1), k, (k+1)}. Say that i and j are connected in a tree t, if the tree contains the edge i-j, or if i and j are brothers and of them is the end of the minimal chain of t. Each of the four ingredients of the previous identity is now decomposed into five terms, depending on whether the nodes (k -1), k, (k + 1) are connected or not, namely: no connectedness; only k, (k + 1) connected; (k -1), k connected; (k -1), (k + 1) connected; all connected. Thus,

f 2n (k -1, k) = [ ❅ ❅ k-1 • , ❅ ❅ k 2n , k + 1] + [ ❅ ❅ k-1 • , ❅ ❅ 2n k k+1 ] + [ ❅ ❅ ❅ 2n k • k-1 , k + 1 ] + [ ❅ ❅ k-1 k+1 • , ❅ ❅ k 2n ] + ❅ ❅ ❅ 2n k k+1 • k-1 := A 1 + A 2 + A 3 + A 4 + A 5 ; f 2n (k + 1, k) = [ ❅ ❅ k+1 • , k -1, ❅ ❅ 2n k ] + [ ❅ ❅ k+1 2n k • , k -1] + [ ❅ ❅ k+1 • , ❅ ❅ ❅ k 2n k-1 ] + [ ❅ ❅ k+1 k-1 • , ❅ ❅ 2n k ] + ❅ ❅ ❅ • k k+1 2n k-1 := B 1 + B 2 + B 3 + B 4 + B 5 ; f 2n (k, k -1) = [ ❅ ❅ k • , k + 1, ❅ ❅ 2n k-1 ] + [ ❅ ❅ k k+1 • , ❅ ❅ 2n k-1 ] + [ ❅ ❅ k 2n k-1 • , k + 1] + [ ❅ ❅ 2n k+1 k-1 , ❅ ❅ k • ] := C 1 + C 2 + C 3 + C 4 ; f 2n (k, k + 1) = [ ❅ ❅ k • , ❅ ❅ k+1 2n , k -1] + [ ❅ ❅ ❅ 2n k+1 • k , k -1 ] + [ ❅ ❅ k k-1 • , ❅ ❅ 2n k+1 ] + [ ❅ ❅ ❅ 2n k+1 k-1 , ❅ ❅ k • ] + ❅ ❅ ❅ 2n k+1 k-1 • k := D 1 + D 2 + D 3 + D 4 + D 5 .
Now, the following identities hold:

A 1 = C 1 , A 2 = C 4 , A 3 = D 2 , A 4 = C 2 , B 1 = D 1 , B 3 = D 4 , B 4 = D 3 , so that i (A i + B i ) -i (C i + D i ) = (B 5 -D 5 ) -(C 3 -A 5 -B 2 ).
As before, we may write B 5 = B 5 (⋆) + B 5 ( \ ), D 5 = D 5 (⋆) + D 5 ( \ ). As B 5 (⋆) = D 5 (⋆) and B 5 ( \ ) = 2 D 5 ( \ ), we get:

(6.6) B 5 -D 5 = D 5 ( \ ) = ❅ ❅ ❅ ❅ • \ 2n k k+1 k-1 = ❅ ❅ ❅ ❅ ❅ ❅ k • \ k-1 k+1 2n ,
as k is supposed to be greater than 3. Next,

C 3 -B 2 = [ ❅ ❅ k 2n k-1 • , k + 1] -[ ❅ ❅ k+1 2n k • , k -1] = ❅ ❅ ❅ • k-1 k 2n k+1 -[ ❅ ❅ ❅ • k-1 k 2n , k + 1] -[ ❅ ❅ ❅ • k k+1 2n , k -1] = ❅ ❅ ❅ • k-1 k 2n k+1 ; C 3 -B 2 -A 5 = ❅ ❅ ❅ • k-1 k 2n k+1 - ❅ ❅ ❅ 2n k k+1 • k-1 := E -F = (E(⋆) -F (⋆)) + (E( \ ) -F ( \ )) = F ( \ ) = ❅ ❅ ❅ ❅ k+1 • \ 2n k-1 k = ❅ ❅ ❅ ❅ ❅ ❅ k-1 2n • \ k k+1 . (6.7)
By comparing the evaluations (6.6) and (6.7) we get: (B 5 -D 5 ) -(C 3 -A 5 -B 2 ) = 0. This completes the proof of (6.5).

The entries f 2n (3, 2) and f 2n (2n -1, 2n -2), belonging to the upper diagonal of the lower triangle matrix M 2n , being evaluated by identity (6.4), and the entries of the upper triangle being known by Theorem 1.4, we can apply the crossing equalities (6.5), starting with k = 3, and obtain all the values of the entries of that upper diagonal. Altogether, besides the entries of the upper triangle, all the entries lying on the border of the lower triangle can be calculated, as illustrated in boldface in the following matrix M 8 .

M 8 = k = 1 2 3 4 5 6 7 f 8 (m, .) m = 2 . . 5

Generating functions for the f 2n (m, k)

The calculation of the generating functions for the f 2n (m, k) is similar to the calculation made for the tangent tree case in a our previous paper [START_REF] Foata | Tree Calculus for Bivariable Difference Equations[END_REF]. Recall the definition and some basic properties of the Poupard matrix. Let G = (g i,j ) (i ≥ 0, j ≥ 0) be an infinite matrix with nonnegative integral entries. Say that G is a Poupard matrix, if for every i ≥ 0, j ≥ 0 the following identity holds: (7.1) g i,j+2 -2 g i+1,j+1 + g i+2,j + 4 g i,j = 0.

Remark. Last coefficient is 4, not 2 as in [START_REF] Foata | Tree Calculus for Bivariable Difference Equations[END_REF].

Let G(x, y) := i≥0, j≥0 g i,j (x i /i!) (y j /j!); R i (y) := j≥0 g i,j (y j /j!)

(i ≥ 0); C j (x) := i≥0 g i,j (x i /i!) (j ≥
0) be the exponential generating functions for the matrix itself, its rows and columns, respectively. The next two lemmas, serving to prove Theorem 1.5, are replica of Propositions 9.1 and 9.2 in [START_REF] Foata | Tree Calculus for Bivariable Difference Equations[END_REF]. Their proofs are omitted.

Lemma 7.1. The following four properties are equivalent.

(i) G = (g i,j ) (i ≥ 0, j ≥ 0) is a Poupard matrix; (ii) R ′′ i (y) -2 R ′ i+1 (y) + R i+2 (y) + 4 R i (y) = 0 for all i ≥ 0; (iii) C ′′ j (x) -2 C ′ j+1 (x) + C j+2 (x) + 4 C j (x)
for all j ≥ 0; (iv) G(x, y) satisfies the partial differential equation:

(7.2) ∂ 2 G(x, y) ∂x 2 -2 ∂ 2 G(x, y) ∂x ∂y + ∂ 2 G(x, y) ∂y 2 + 4 G(x, y) = 0.
Lemma 7.2. Let G(x, y) be the exponential generating function for a Poupard matrix G. Then,

(7.3) G(x, y) = A(x + y) cos(2 y) + B(x + y) sin(2 y),
where A(y) and B(y) are two arbitrary series.

The entries of the upper triangles of the matrices (M 2n ) (see Table 1.2) are now recorded as entries of infinite matrices (Ω (p) ) (p ≥ 1) by

(7.4) ω (p) i,j := 0, if i + j ≡ p mod 2; f 2n (m, k), if i + j ≡ p mod 2; with m := p + 1, k := p + j + 2, 2n := p + i + j + 3. Conversely, i := 2n -k -1, j := k -m -1, p := m -1.
In particular, the first one Ω (1) = (ω (1) i,j ) (i, j ≥ 0) contains the first rows of the upper triangles, displayed as counter-diagonals. Furthermore, a counter-diagonal with zero entries is placed between two successive rows. The row labeled i of Ω (p) will be denoted by Ω i,j y j /j!. Also, Ω (p) (x, y) := i≥0 Ω (p) i,• (y)x i /i! will be the double exponential generating function for the matrix Ω (p) . Proposition 7.4. For all p ≥ 1 we have: This is true by Theorem 1.2.

Ω (1) =             0 1 2 3 4 5 6 7 0 f 4 (2, 3) 0 f 6 (2, 5) 0 f 8 (2, 7) 0 f 10 (2, 9) 0 1 0 f 6 (2, 4) 0 f 8 (2, 6) 0 f 10 (2, 8) 0 • • • 2 f 6 (2, 3) 0 f 8 (2, 5) 0 f 10 (2, 7) 0 • • • 3 0 f 8 (2, 4) 0 f 10 (2, 6) 0 • • • 4 f 8 (2, 3) 0 f 10 (2, 5) 0 • • • 5 0 f 10 (2, 4) 0 • • • 6 f 10 (2, 3) 0 • • • 7 0 • • •             =            
As x and y play a symmetric role in (7.3), the solution in (7.3) may also be written G(x, y) = A(x + y) cos(2 x) + B(x + y) sin(2 x), so that the generating function of each matrix Ω (p) is of the form Ω (p) (x, y) = A(x + y) cos(2 x) + B(x + y) sin(2 x).

Hence, Ω (p) (x, y) First, make the evaluation of Ω (1) (x, y). The row labeled 0 of the matrix Ω (1) reads: 1, 0, 1, 0, 5, 0, 61, . . . , which is the sequence of the coefficients of the Taylor expansion of sec y. Thus, Ω

  showing that the components fall in three categories: (1) B 2 and B 4 having one subtree to determine; (2) C 2 and A 2 having two such subtrees; (3) D 2 , B 3 and B 5 having three of them.

=

  Every matrix Ω (p) (p ≥ 1) is a Poupard matrix.Proof. Using Definition (7.4) we haveω f 2n+2 (m, k + 2) -2 f 2n+2 (m, k + 1) + f 2n+2 (m, k) + 4 f 2n (m, k) = ∆ k f 2n+2 (m, k) + 4 f 2n (m, k) = 0,by rule (R 2).

  and the exponential generating function for that row by Ω(p) i,• (y) = j≥0 ω (p)

  For the first identity it suffices to prove ω , that isf 2n (m, 2n -1) = f 2n (2, 2n + 1 -m).This is true by the symmetry property of the Poupard triangle, as proved in Corollary 1.3 in[START_REF] Foata | Finite difference calculus for alternating permutations[END_REF]. For the second identity it suffices to prove ω , that is f 2n (m, 2n -2) = 3f 2n (m, 2n -1).

  (y) = A(y). Also,(∂/∂x)Ω (p) (x, y) = ((∂/∂x)A(x + y)) cos(2 x) + A(x + y)(-2) sin(2 x) + ((∂/∂x)B(x + y)) sin(2 x) + B(x + y) 2 cos(2 x) and ∂ ∂x Ω (p) (x, y) {x = 0} = ∂ ∂x A(x + y) {x = 0} +2 B(x + y) {x = • (y). Hence, (7.5) Ω (p) (x, y) = cos(2 x) Ω (1) p-1,• (x + y) + sin(2 x) ∂ ∂y Ω(1)p-1,• (x + y).

  (y) = sec y. Taking p = 1 in (7.5) we get Ω (1) (x, y) = sec(x + y) cos(2 x) + sec(x + y) tan(x + y) sin(2 x) = cos(x -y) cos 2 (x + y) . (7.6) For further use let us also calculate the partial derivative of Ω (1) (x, y) with respect of y:∂ ∂y Ω (1) (x, y) = 1 cos 3 (x + y) sin(x -y) cos(x + y) + 2 cos(x -y) sin(x + y) p-1,• (x + y) z p-1 (p -1)! + sin(2x) ∂ ∂y p≥1 Ω(1)p-1,• (x + y) z p-1 (p -1)!

Table 6 .

 6 1: the matrix M 8 , bold-faced entries analytically evaluated.

				15 21 15 5	61
	3 5 10	. 45 63 45 15	183
	4 15 35 50	. 101 63 21	285
	5 21 54 86 106	. 45 15	327
	6 15 46 82 87 50	. 5	285
	7 5 22 46 60 40 10	.	183
	8	. 16 16 14 10	5	.	61
	f 8 (., k) 61 183 285 327 285 183 61 E 8 = 1385

= cos(2x) Ω (1) (z, x + y) + sin(2x) ∂ ∂y Ω (1) (z, x + y)

.10) the latter sum over the set {3 ≤ m + 1 ≤ k ≤ 2n -1}. We have proved Theorem 1.5.


Yann Bugeaud

Guo-Niu Han

A combinatorial proof of the non-vanishing of Hankel determinants of the Thue-Morse sequence

In 1998, Allouche, Peyrière, Wen and Wen established that the Hankel determinants associated with the Thue-Morse sequence on {-1, 1} are always nonzero. Their proof depends on a set of sixteen recurrence relations. We present an alternative, purely combinatorial proof of the same result. We also re-prove a recent result of Coons on the non-vanishing of the Hankel determinants associated to two other classical integer sequences.

Introduction

Let C(z) be a power series in one variable with rational coefficients, be the (p, k)-order Hankel determinant associated to C(z). For simplicity, we write H k (C) instead of H 0 k (C). The study of the non-vanishing of (p, k)-order Hankel determinants is an interesting question on its own, and this is the purpose of the present paper for the sequence (c k ) k≥0 being the Thue-Morse sequence. However, we start the introduction by pointing out a motivation coming from Diophantine approximation and concerning the study of rational approximation to the real numbers C(1/b), where b ≥ 2 is an integer.

C(z) = k≥0 c k z k , c k ∈ Q.
Let ξ be an irrational, real number. The irrationality exponent µ(ξ) of ξ is the supremum of the real numbers µ such that the inequality ξ -p q < 1 q µ 2000 Mathematics Subject Classification : 05A05, 11J82.

1 has infinitely many solutions in rational numbers p/q. It follows from the theory of continued fractions that µ(ξ) is always greater than or equal to 2, and an easy covering argument shows that µ(ξ) is equal to 2 for almost all real numbers ξ (with respect to the Lebesgue measure). Furthermore, Roth's theorem asserts that the irrationality exponent of every algebraic irrational number is equal to 2. The reader is directed to the monograph [START_REF] Schmidt | Diophantine Approximation[END_REF] for proofs and refinements of these assertions. It is in general a very difficult problem to determine the irrationality exponent of a given transcendental real number ξ, unless ξ is given by its continued fraction expansion. Apart from more or less ad hoc constructions, there are only very few examples of transcendental numbers ξ whose irrationality exponent is known. When they can be applied, the current techniques allow us most often only to get an upper bound for µ(ξ).

Recently, Bugeaud [START_REF] Bugeaud | On the irrationality exponent of the Thue-Morse-Mahler numbers[END_REF] developed a method for computing µ(ξ) when ξ is a Thue-Morse-Mahler number. Let t = t 0 t 1 t 2 . . . = 1 -1 -1 1 -1 1 1 -1 -1 1 1 -1 . . . denote the Thue-Morse word on {-1, 1} defined by t 0 = 1, t 2k = t k and t 2k+1 = -t k for k ≥ 0. Alternatively, t k = 1 (resp. -1) if the number of 1's in the binary expansion of k is even (resp. is odd). Let T (z) := k≥0 t k z k be the generating function of (t k ) k≥0 . It is proved in [START_REF] Bugeaud | On the irrationality exponent of the Thue-Morse-Mahler numbers[END_REF] that, for every integer b ≥ 2, the irrationality exponent of the real number

T (1/b) = k≥0 t k b k = 1 - 1 b - 1 b 2 + 1 b 3 - 1 b 4 + 1 b 5 + . . .
is equal to 2. There are two main ingredients in the proof. A first one is the fact that T (z) satisfies a functional equation, namely

T (z) = (1 -z)T (z 2 ) = n≥0 1 -z 2 n ,
a key tool in Mahler's proof [START_REF] Mahler | Arithmetische Eigenschaften der Lösungen einer Klasse von Funktionalgleichungen[END_REF] that T (1/b) is transcendental.

A second one is the non-vanishing of Hankel determinants associated with t, a result established by Allouche, Peyrière, Wen and Wen [START_REF] Allouche | Hankel determinants of the Thue-Morse sequence[END_REF].

Theorem APWW. For every positive integer k, the Hankel determinant H k (T ) is nonzero.

The proof given in [START_REF] Allouche | Hankel determinants of the Thue-Morse sequence[END_REF] is long and difficult. It depends on a set of sixteen recurrence relations involving the (p, k)-order Hankel determinants and gives additional results on the values of the Hankel determinants H p k (T ). Subsequently, Coons [START_REF] Coons | On the rational approximation of the sum of the reciprocals of the Fermat numbers[END_REF] considered the functions

F (z) := k≥1 f k z k = ∞ n=0 z 2 n 1 + z 2 n and G(z) := k≥1 g k z k = ∞ n=0 z 2 n 1 -z 2 n . (1.1)
He proved that, for every integer b ≥ 2, the irrationality exponent of F (1/b) and G(1/b) is equal to 2. To this end, he followed the method of [START_REF] Bugeaud | On the irrationality exponent of the Thue-Morse-Mahler numbers[END_REF], replacing the use of Theorem APWW by that of the next result (Theorem 2 of [START_REF] Coons | On the rational approximation of the sum of the reciprocals of the Fermat numbers[END_REF]).

Theorem C. For every positive integer k, the Hankel determinants

H 1 k (F ) and H 1 k (G) are nonzero.
Coons' proof of Theorem C is of the same level of difficulty as the one of Theorem APWW. It is long and hard to follow.

The aim of this note is to provide a unified, combinatorial proof of both Theorems APWW and C. We believe that our approach is much simpler than that of [START_REF] Allouche | Hankel determinants of the Thue-Morse sequence[END_REF][START_REF] Coons | On the rational approximation of the sum of the reciprocals of the Fermat numbers[END_REF].

Our paper is organized as follows. The key combinatorial result, namely Theorem J, is stated in Section 2, along with three equivalent lemmas. Complete proofs of these lemmas and theorem are given in Section 3. We gather in Section 4 some additional statements, which follow from our approach. Then, in Section 5, we show how Theorems APWW and C can be easily derived from Theorem J.

When nothing else is specified, the notation a ≡ b means that the integers a and b are congruent modulo 2.

Permutations and involutions

Throughout this text, N denotes the set of non-negative integers. We introduce the sets

J = {(2n + 1)2 2k -1 | n, k ∈ N } = {0,
K = N \ J = {1, 5, 7, 9, 13, 17, . . .} = {(2n + 1)2 2k+1 -1 | n, k ∈ N }.
Let Sym m = Sym {0,1,...,m-1} be the set of all permutations on {0, 1, . . . , m -1}. In this section we prove the following result.

Theorem J.

(J1) For every integer m ≥ 1, the number of permutations σ ∈ Sym m such that i + σ(i) ∈ J for i = 0, 1, . . . , m -1, is an odd number.

(J2) For every integer m ≥ 1, the number of permutations σ ∈ Sym m such that i + σ(i) ∈ J for i = 0, 1, . . . , m -2 (no constraint on m -1 + σ(m -1) ∈ N ) is an odd number.

The proof is based on some combinatorial techniques. Since we want to enumerate permutations modulo 2, we can delete suitable pairs of permutations and the result will not be changed. The problem is then how to associate a given permutation with another to form a pair. Two methods are used in the present paper:

(1) taking the inverse σ -1 of a given permutation σ;

(2) exchanging two values by letting σ(i) := σ(j) and σ(j) := σ(i).

Those two methods are fully described in the proof of Theorem (J1).

Throughout this paper we use three representations for permutations: the one-line, two-lines and the product of disjoint cycles. For example, we write σ ∈ Sym 9 = 516280374 = 012345678 516280374 = (0, 5)(1)(2, 6, 3)(4, 8)(7).

We choose to separate the elements of a cycle by commas. Sometimes we write a list of sets under the two-line representations. If the set A is under the index i, this means that i + σ(i) ∈ A. For example, the permutations in (J1) and (J2) are   0 1 2 3 4 5 6 7 8

• • • • • • • • • J J J J J J J J J   and   0 1 2 3 4 5 6 7 8 • • • • • • • • • J J J J J J J J N   respectively.
An involution is a permutation σ such that σ = σ -1 . In the cycle representation of an involution every cycle is either a fixed point (b) or a transposition (c, d). For every set A, a transposition (c, d) is said to be an A-transposition if c + d ∈ A and c + d is odd. This means also that there is an even number and an odd number in every A-transposition. Generally the order of the two numbers in a transposition does not matter. However, throughout this paper, we always write the even number before the odd number in every A-transposition.

For finite sets of positive integers A, B and a non-negative integer f , let ν(A, f, B) be the number of involutions in Sym A such that all transpositions are B-transpositions and have exactly f fixed points. Also let ν(A, f /g, B) = ν(A, f, B) + ν(A, g, B). For an infinite set A let A| m be the set composed of the m smallest integers in A.

We state below three equivalent lemmas. The first (resp. second, third) assertion of any of these is equivalent to the first (resp. second, third) assertion of any of the other two lemmas.

Lemma N. For m ≥ 1 we have

ν(N | m , 0/1, K) ≡ 1; (N 1) ν(N | 2m-1 , 1, J) ≡ 1; (N 2) ν(N | 2m , 0/2, J) ≡ 1. (N 3) Let P = {0, 3, 4, 7, 8, 11, . . .} = {k | k = 0, 3 (mod 4)} and Q = {1, 2, 5, 6, 9, 10, . . .} = {k | k = 1, 2 (mod 4)}.
We define three transformations:

β : N → N ; k → k/2 if k is even (k -1)/2 if k is odd γ : P → N ; k → k/4 if k is even (k -3)/4 if k is odd δ : N → N ; k → k + 1 if k is even k -1 if k is odd
The transformation β is extended to the involutions σ on N | m such that all transpositions are K-transpositions, by applying β on every number in the cycle representation of σ. The transformation β for involutions is reversible, even though β on N is not reversible. For example β((7)(0, 5)(6, 3

)(2)(8, 1)(4)) = (3)(0, 2)(3, 1)(1)(4, 0)(2).
We do not know a priori whether the fixed point 3 is obtained from 6 or from 7. We must look at the transposition (3, 1) first. It is obtained from the permutation (6, 3) since we know that an even number is always before an odd number in the transposition. Thus, we can recover the K-transpositions (6, 3)(0, 5)(8, 1). All the other numbers are fixed points, so these are (7

)(2)(4). If (c, d) is a K-transposition, then β(c) + β(d) = c + d -1 2 = (2n + 1)2 2k+1 -1 -1 2 = (2n + 1)2 2k -1 ∈ J.
In the same way, the transformation γ is extended to the involutions σ on P | m such that all transpositions are J-transpositions, by applying γ on every number in the cycle representation of σ. Again, the transformation γ for involutions is reversible, even though γ on P | m is not reversible. For example

γ((15)(0, 11)(12, 7)(4)(16, 3)(8)) = (3)(0, 2)(3, 1)(1)(4, 0)(2). If (c, d) is a J-transposition and c, d ∈ P , then γ(c) + γ(d) = c + d -3 4 = (2n + 1)2 2k -1 -3 4 = (2n + 1)2 2k-2 -1 ∈ J.
In fact we can check that the image sets of β and γ are identical, thus the transformation γ -1 β is well defined. The above comments are still valid if J and K are exchanged. By the bijection γ -1 β, the following lemma is equivalent to Lemma N.

Lemma P. For m ≥ 1 we have

ν(P | m , 0/1, J) ≡ 1; (P 1) ν(P | 2m-1 , 1, K) ≡ 1; (P 2) ν(P | 2m , 0/2, K) ≡ 1. (P 3)
The third transformation δ is extended to the set of involutions σ on P | m such that all the transpositions are J-transpositions, by applying δ on every number in the cycle representation of σ. The transformation δ for involutions is reversible since δ for N is reversible. For example

δ((15)(0, 11)(12, 7)(4)(16, 3)(8)) = (14)(1, 10)(13, 6)(5)(17, 2)(9) If (c, d) is a J-transposition then (δ(c), δ(d)) is still a J-transposition since c + d = δ(c) + δ(d).
The above comments are still valid if J and K are exchanged. Using the bijection δ, we see that the following lemma is equivalent to Lemma P.

Lemma Q. For m ≥ 1 we have ν(Q| m , 0/1, J) ≡ 1; (Q1) ν(Q| 2m-1 , 1, K) ≡ 1; (Q2) ν(Q| 2m , 0/2, K) ≡ 1. (Q3)
Since Lemmas N , P and Q are equivalent, we prove (P1), (N2), (N3) in Section 3.

The proofs

We begin with several comments. The proofs of all the theorems and lemmas are based on induction on the lengths of the permutations. Small values of m can be easily checked by hand. The proof of (N 2) uses (P 1), the proof of (P 1) uses (J2), and the proof of (J2) uses again (N 2). This is not a circular reasoning, because the length of permutations is smaller than the length of the original permutations. For every permutation σ, we say that σ contains a column odd even (in the two-line representation) if there is some odd number j such that σ(j) is even. We make similar sentence pour even even , even odd and odd odd . For short we say that a permutation σ is "in (J1)" if σ satisfies the conditions described in the statement of Theorem (J1), and that an involution σ is "in (P1)" if σ is an involution on the set P | m having 0 or 1 fixed point, and all transpositions are J-transpositions. The following basic facts are easy to verify: (FJ1) The set J contains all even numbers; (FJ2) If an odd number x is in J, then x ≡ 3 (mod 4).

Proof of (J1). -We count the permutations in (J1) modulo 2. If σ contains more than two columns odd odd in the two-line representation, select the first two such columns i 1 j 1 and i 2 j 2 . We define another permutation τ obtained from σ by exchanging j 1 and j 2 in the bottom line. This procedure is reversible. By (FJ1), it is easy to verify that τ is also a valid permutation in (J1). So that we can delete the pair σ and τ , and there only remain the permutations containing 0 or 1 column odd odd , in particular, having 0 or 1 odd fixed point. Similarly with an even number, there only remain permutations containing 0 or 1 column even even . Consequently, the only remaining permutations have 0, 1 or 2 fixed points. Thanks to the bijection σ → σ -1 , we need only consider the involutions. We can check that all transpositions are J-transpositions. If m is odd, then the involution contains one fixed point, and the number of such involutions is ν(N | m , 1, J) ≡ 1 by Lemma (N 2). If m is even, then the involution may contain 0 or 2 fixed points, and in the case of 2 fixed points, we can check that there are exactly one odd and one even fixed point. Hence the number of such involutions is ν(N | m , 0/2, J) ≡ 1 by Lemma (N 3).

Proof of (N 2) and (N 3). -By (FJ2) the two numbers in every J-transposition are either both in P or both in Q. This means that no J-transposition takes one number in P and another in Q. The involutions in (N 2) and (N 3) are of type

P Q (•)(••)(••)(••) (•)(•)(••)(••)(••)(••)
The two parts composed by numbers from P and from Q are "independent". The cardinalities of the two parts and the number of fixed points in each side are characterized by m. If m = 2k + 1 is odd, then every involution σ in (N 2) has exactly one fixed point, in P | k or Q| k+1 , according to the parity of k. Hence

ν(N | 2k+1 , 1, J) ≡ ν(P | k , 0/1, J) × ν(Q| k+1 , 0/1, J) ≡ 1.
The last equality follows from Lemmas (P 1) and (Q1). If m = 2k is even and k is odd, then the cardinalities of P | k and Q| k are odd. So that there is one fixed point in P | k and one in Q| k . Hence ν(N | 2k , 0, J) = 0 and

ν(N | 2k , 2, J) ≡ ν(P | k , 1, J) × ν(Q| k , 1, J) ≡ 1.
Again, the last equality follows from Lemmas (P 1) and (Q1

ν(N | 2k , 0, J) ≡ ν(P | k , 0, J) × ν(Q| k , 0, J) ≡ 1, ν(N | 2k , 2, J) ≡ ν(P | k , 0, J) × ν(Q| k , 2, J) + ν(P | k , 2, J) × ν(Q| k , 0, J) ≡ 0.
The first equality follows from Lemmas (P 1) and (Q1). The second equality is proved by using the bijection δ described in Section 2.

Proof of (P1).

-When m = 2k is even, the image τ = γ(σ) by γ (described in Section 2) of every permutation σ in (P 1) can be identified with a permutation ρ on {0, 1, . . . , k-1} such that i + ρ(i) ∈ J for i = 0, 1, . . . , k -1. For example, taking σ = (0, 3)(7, 8)(4, 11), we have τ = γ(σ) = γ((0, 3)(8, 7)(4, 11)) = (0, 0)(2, 1)(1, 2) which can be identified with the permutation on {0, 1, 2} given by ρ = 0 1 2 0 2 1 .

The number of such permutations is odd by Theorem (J1). When m = 2k + 1 is odd, every permutation σ in (P 1) has one fixed point. Apply the transformation γ to σ, then replace the unique singleton b (which is obtained from the fixed point of σ) by (k, b) or (b, k) to form a pair. There is a unique way to choose between (k, b) and (b, k) such that τ can be identified to a permutation ρ on {0, 1, . . . , k}. For example take σ = (0, 11)(7, 8)(3, 12)(4), we have τ = γ(σ) = γ((0, 11)(8, 7)(12, 3)(4)) = (0, 2)(2, 1)(3, 0)(1), the single element is b = 1, we need replace (1) by (1, 3) (not (3, 1) of course). So that τ is identified to the following permutation on {0, 1, 2, 3}

ρ =   0 1 2 3 2 3 1 0 J N J J   or its inverse ρ -1 =   0 1 2 3 3 2 0 1 J J J N   .
We can verify that one of the two permutations ρ and ρ -1 is in (J2) (look at the letter N at the third line in the above examples). The number of such permutions is odd by Theorem (J2).

Proof of (J2). -For every permutation σ in (J2), i + σ(i) ∈ J for i ≤ m -2. If σ(m -1) is odd and σ contains a odd odd column, let j σ(j) be the first odd odd column. We then define another permutation τ obtained from σ by exchanging σ(j) and σ(m -1). This procedure is reversible. We can delete the pair σ and τ . Similarly we can delete every permutation σ such that σ(m -1) is even and σ contains an even even column. There only remain two types of permutations. If σ(m -1) is odd, then every number under an odd number in the two-line representation is even. If σ(m -1) is even, then every number under an even number is odd, as shown here:

1 2 3 4 5 • • • | m -1 e e e • • • | o and 0 1 2 3 4 • • • | m -1 o o o • • • | e
The letter "e" and "o" represent an even and odd numbers respectively. There are two cases to be considered. (I.2) If σ(m -1) is odd, then there are as many even numbers as odd numbers. Since the last column is odd odd , there is necessarily a unique column even even , which will be called "intruder", and marked by the * sign. The permutations in (J2) are of type * even The first factor is equal to ν(N | m , 2, J) and the second one is equal to ν(N | m-1 , 1, J) ≡ 1 by (N2). By (I.1) and (I.2) the total number of permutations in this case is

ν(N | m , 0, J) × ν(N | m-1 , 1, J) + ν(N | m , 2, J) × ν(N | m-1 , 1, J) ≡ ν(N | m , 0/2, J) ≡ 1,
where the last equality follows from (N3). The first factor counts the number of involutions of N | m-1 with 2 fixed points. Their number is equal to ν(N | m-1 , 2, J). The second factor is equal to ν(N | m , 1, J) ≡ 1 by (N2). By (II.1) and (II.2) the total number of permutations in this case is

ν(N | m-1 , 0, J) × ν(N | m , 1, J) + ν(N | m-1 , 2, J) × ν(N | m , 1, J) ≡ ν(N | m-1 , 0/2, J) ≡ 1,
where the last equality follows from (N3).

Further results

For subsets

A, B, C, D of N let A B C D m denote the number of permutations σ in Sym m such that i + σ(i) ∈      A, if i, σ(i) ∈ [0, m -2] B, if i ∈ [0, m -2], σ(i) = m -1 C, if i = m -1, σ(i) ∈ [0, m -2] D, if i = σ(i) = m -1. Theorem D. For every m ≥ 1, we have J J J J m ≡ 1, (J1) J N J N m ≡ 1, (J2) J N N N m ≡ m, (J3) K K K K m ≡ m + 1, (K1) K N K K m ≡ m + 1, (K2) K N N K m ≡ m + 1. (K3)
Remark 1. The following basic facts are easy to verify: (FK1) The set K contains no even integer; (FK2) The set K contains all integers of the form 4n + 1; Remark 2. Since J contains all even numbers, taking D = J is equivalent to taking D = N ; Since K does not contain any even number, taking D = K is equivalent to taking D = ∅. Remark 3. Formula (K1) implies that the Hankel determinants of the series

K(z) = 1 1 -z + k≥0 z 2 n -1 1 -z 2 n satisfies H m (K) ≡ m + 1 for m ≥ 1.
Remark 4. The formulas in Theorem D can be used to derive other formulas, for example

(Ex) J K K J m ≡ m.
Proof of (Ex). -We have

J N N ∅ m ≡ J N N N m - J J J J m-1 ≡ m -1 [By (J3) and (J1)], (Ex1)
J N J ∅ m ≡ J N J N m - J J J J m-1 ≡ 1 -1 ≡ 0, (Ex2) J J J ∅ m ≡ J J J N m - J J J J m-1 ≡ 1 -1 ≡ 0, (Ex3) J N K ∅ m ≡ J N N ∅ m - J N J ∅ m ≡ (m -1) -0 ≡ m -1, (Ex4) J J K ∅ m ≡ J J N ∅ m - J J J ∅ m ≡ 0 -0 ≡ 0, (Ex5) J K K ∅ m ≡ J N K ∅ m - J J K ∅ m ≡ (m -1) -0 ≡ m -1, (Ex6) J K K J m ≡ J K K ∅ m + J J J J m-1 ≡ (m -1) + 1 ≡ m. (Ex)
The first two identities (J1) and (J2) are simply reproduced from Theorem J.

Proof of (J3). -By the same arguments as in the proof of (J1), the permutations to enumerate are the involutions σ such that (i) σ has 0, 1, 2 fixed points;

(ii) every transposition in σ is a J-transposition, except the one which contains m -1, if it exists;

(iii) If m -1 is in a transposition (m -1, b), then m -1 + b is odd. The number of permutations of the type given by the first factor is equal to ν(N | m-1 , 0, K) ≡ 1 and that of the type given by the second one is equal to ν(N | m , 1, K) ≡ 1 by (N1). Hence

K N K N m ≡ 1 and K N K K m ≡ K N K N m - K K K K m-1 ≡ 1 -(m -1 + 1) ≡ m + 1.
Proof of (K3). -We need only count the involutions without fixed points, so that the number of such permutations is 0 when m is odd. If m = 2k is even, all transpositions are necessarily K-transpositions, except the one which contains m -1. Removing m -1 yields an involution with one fixed point. The number of such involutions is ν(N | m-1 , 1, K) ≡ 1 by (N1). Furthermore, in Lemma (N3) we have a mixed formula for 0 or 2 fixed points. From the proof of (N 2) and (N 3) we can separate it into two more precise formulas.

Lemma N'. We have

ν(N | 2k , 0, J) ≡ k + 1, (N 4) ν(N | 2k , 2, J) ≡ k. (N 5)
Using the transfomations β, γ, δ, we see that Lemma N' is equivalent to Lemma P'. We have

ν(P | 2k , 0, K) ≡ k + 1, (P 4) ν(P | 2k , 2, K) ≡ k. (P 5) Lemma Q'. We have ν(Q| 2k , 0, K) ≡ k + 1, (Q4) ν(Q| 2k , 2, K) ≡ k. (Q5)

Completion of the combinatorial proofs of Theorems APWW and C

Recall that First, we notice that, for k ≥ 1, the integer g k is equal to the 2-adic valuation of 2k, known sometimes as the ruler function. For k ≥ 1, we have the recursion

J = {(2n + 1)2 2k -1 | n, k ∈ N } = {0,
g 2k+1 = 1
and

g 2k = 1 + g k .
This sequence starts as

(g k ) k≥1 = 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 4, . . .
The proofs of Theorems APWW and C combine Theorem J with the next two lemmas.

Lemma 1. For k ≥ 0, the integer g k+1 is odd if, and only if, k is in J.

Proof. Let k be a non-negative integer. It follows from (1.1) that g k+1 is equal to the number of pairs (j, m) of integers j ≥ 1, m ≥ 0 such that j2 m = k + 1. In particular, writing k + 1 = j 0 2 m 0 with j 0 odd, we see that

k + 1 = j 0 2 m 0 = (2j 0 )2 m 0 -1 = . . . = (2 m 0 j 0 )2 0 ,
showing that g k+1 = m 0 + 1. Consequently, g k+1 is odd if, and only if, m 0 is even, that is, if and only if, k is in J.

Lemma 2. For k ≥ 0, the integer δ k := (t k+1t k )/2 is odd if, and only if, k is in J.

Proof. For ℓ ≥ 0, we have δ 2ℓ = (t 2ℓ+1t 2ℓ )/2 = -t ℓ = ±1, thus δ 2ℓ is odd. For an odd integer j ≥ 1 and an integer k ≥ 1, we have

δ j2 2k -1 ≡ (t j2 2k -t j2 2k -1 )/2 ≡ (t j2 2k-1 + t j2 2k-1 -1 )/2 ≡ 1 + δ j2 2k-1 -1 (mod 2)
and, likewise, δ j2 2k-1 -1 ≡ 1 + δ j2 2(k-1) -1 (mod 2).

Consequently, an immediate induction shows that, for any odd integer j and any integer ℓ ≥ 0, the integer δ j2 ℓ -1 is odd if, and only if, ℓ is even, that is, if, and only if, j2 ℓ -1 is in J. This proves the lemma.

Proof of Theorem C. Let J (z) be the power series where inv(σ) is the number of inversions of σ. The product j 0+σ(0) j 1+σ(1) • • • j k-1+σ(k-1) is equal to 1 if i + σ(i) ∈ J for i = 0, 1, . . . , k -1, and is equal to 0 otherwise. Hence, the above Hankel determinant H k (J ) is equal modulo 2 to the number of permutations σ ∈ Sym k such that i + σ(i) ∈ J for all i = 0, 1, . . . , k -1, which is equal to 1 modulo 2 by Theorem (J1). We deduce from Lemma 1 that H k (J ) ≡ H

J (z) =

For k ≥ 1

 1 and p ≥ 0, let H p k (C) := c p c p+1 . . . c p+k-1 c p+1 c p+2 . . . c p+k . . . . . . . . . . . . c p+k-1 c p+k . . . c p+2k-2

(

  I) If m is even, then m -1 is odd. The number of odd numbers in N | m is equal to the number of even numbers in N | m . (I.1) If σ(m -1) is even, then the permutations are of the type The first factor is equal to ν(N | m , 0, J), and the second factor is equivalent to counts ν(N | m-1 , 1, J) ≡ 1 by (N2).

  The column 2 is the "intruder", and the letter J under that column can be replaced by N . Exchanging σ( * ) and σ(m -1) yields * even

  (II) If m is odd, then m -1 is even. The number of even numbers in N | m is equal to the number of odd numbers in N | m , plus 1. (II.1) If σ(m -1) is even, then the permutations are of type The first factor is equal to ν(N | m-1 , 0, J), and the second factor is equivalent to The number of such permutations is equal to ν(N | m , 1, J), which is odd, by (N2). (II.2) If σ(m -1) is odd, the permutations are of type * even Exchanging σ( * ) and σ(m -1) yields * even

(J3. 1 )

 1 If m is odd, then there is exactly one fixed point. If m -1 is this fixed point, then the number of involutions is ν(N | m-1 , 0, J). If m -1 is in a transposition (b 1 , m -1) and the fixed point is (b 2 ), then deleting m -1 is a transformation reversible. We get an involution of Sym m-1 with two fixed points b 1 , b 2 . The number of such involutions is ν(N | m-1 , 2, J). Hence the total number of involutions is ν(N | m-1 , 0, J)+ν(N | m-1 , 2, J) = ν(N | m-1 , 0/2, J),which is an odd number by Theorem (N3). (J3.2) If m is even, three situations have to be considered. (i) If the involution σ has no fixed point, then the number of involutions is ν(N | m-1 , 1, 0). (ii) If the involution σ has 2 fixed points and m -1 is a fixed point, then the number of involutions is also ν(N | m-1 , 1, 0). (iii) If m -1 is in a transposition (m -1, b 1 ) and the two fixed points are (b 2 ) and (b 3 ), then b 2 + b 3 is odd. Exchanging b 1 with b 2 (resp. b 3 ) if b 2 ≡ b 1 (mod 2) (resp. b 3 ≡ b 1 (mod 2)) is a transformation reversible. Hence the total number of involutions is equal to ν(N | m-1 , 1, 0) + ν(N | m-1 , 1, 0) plus an even number, which is 0 modulo 2.Proof of (K1). -By (FK1) every permutation in (K1) contains no fixed point. Since we need only count the involutions, the number of such permutations is 0 if m is odd. If m = 2k is even, the permutations are of type The two factors are equal to ν(N | m , 0, K) ≡ 1 by (N1).Proof of (K2). -If m is even, all permutations σ in KThe number of permutations of the type given by the first factor is equal to ν(N | m , 0, K) ≡ 1 and that of the type given by the second one is equal to ν(N | m-1 , 1, K) ≡ 1 by (N1).If m is odd, all permutations σ in

  2, 3, 4, 6, 8, 10, 11, . . .} and K = N \ J = {1, 5, 7, 9, 13, 17, . . .} = {(2n + 1)2 2k+1 -1 | n, k ∈ N }.

k≥0 j k z k = 1 +(- 1 )

 11 z 2 + z 3 + z 4 + z 6 + . . . defined by j k = 1 if k ∈ J and j k = 0 otherwise. Let k be a positive integer. By the definition of the determinant, H k (J ) is equal toσ∈Sym k inv(σ) j 0+σ(0) j 1+σ(1) • • • j k-1+σ(k-1) ,

  ). If m = 2k is even and k is even, then the cardinalities of P | k and Q| k are even. Three situations may occur: (i) no fixed point neither in P | k nor in Q| k ; (ii) two fixed points in P | k and no fixed point in Q| k ; (iii) two fixed points in Q| k and no fixed point in P | k . Hence, we get

  1 k (G). Consequently, the Hankel determinant H 1 k (G) is always an odd integer. Furthermore, it follows from (1.1) that the coefficients of the power series F (z) and G(z) are congruent modulo 2. This implies thatH 1 k (F ) ≡ H 1 k (G), proving that the Hankel determinant H 1 k (F ) is always an odd integer.Proof of Theorem APWW.Let k be a positive integer and consider the Hankel determinant H k (T ) of the matrix For j = 1, . . . , k -1, subtracting the (j + 1)-th column from the j-th column, we see thatH k (T ) is equal to the determinant of the matrix k-1t k t kt k+1 . . . t 2k-3t 2k-2 t 2k-2By Lemma 2, this determinant is equal to 2 k-1 times an integer which has the same parity as the determinant of the matrix

				t 0	t 1 . . . t k-1	
			  	t 1 . . .	t 2 . . . . . . . . .	. . .	t k	   .
				t k-1 t k . . . t 2k-2
		t 0 -t 1	t 1 -t 2	. . . t k-2 -t k-1	t k-1	
	  	t 1 -t 2 . . .	t 2 -t 3 . . .	. . . . . .	t k-1 -t k . . .	. . .	t k	   .
			j 0	j 1 . . . j k-2 t k-1	
		  	j 1 . . .	j 2 . . . j k-1 . . . . . . . . .	. . .	t k	   ,

t j k-1 j k . . . j 2k-3 t 2k-2

where j 0 , j 1 , . . . are defined in the proof of Theorem C. Now, we apply Theorem (J2) to deduce that the determinant of the latter matrix is an odd integer. It then follows that the Hankel determinant H k (T ) is a nonzero integer.


Joan Sol Roo

Renaud Gervais

Martin Hachet

Inner Garden: an Augmented Sandbox Designed for Self-Reflection

scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.