Séminaire Lotharingien de Combinatoire 73 (2016), Article B73e

André Permutation Calculus: a Twin Seidel Matrix Sequence

Dominique Foata and Guo-Niu Han

Abstract. Entringer numbers occur in the André permutation combinatorial set-up under several forms. This leads to the construction of a matrix refinement of the tangent (respectively secant) numbers. Furthermore, closed expressions for the three-variate exponential generating functions for pairs of so-called Entringerian statistics are derived.

1. Introduction

1. Entringer numbers

2. André permutations

3. Statistics on André permutations

4. A further bijection between André permutations

5. The Twin Seidel matrix sequence

6. Tight and hooked permutations

7. Trivariate generating functions

2. From Alternating To André Permutations Of The First Kind
3. The Bijection ϕ Between André I And André II Permutations
4. The Bijection g From The Set Of André I Permutations Onto Itself
5. The Proof Of Theorem 1.1 (iii) And (iv)
6. Combinatorics Of The Twin Seidel Matrix Sequence

1. The first evaluations

2. Tight and not tight André I Permutations

3. Hooked and unhooked Permutations

4. A Bijection between B_{n}(m, k) and NH_{n}(m + 1, k)

7. The Making Of Seidel Triangle Sequences

1. The Seidel tangent-secant matrix

2. The generating function for the Entringer numbers

3. Seidel triangle sequences

8. Trivariate Generating Functions

1. The upper triangles of Twin^{(1)}

2. The upper triangles of Twin^{(2)}

3. The bottom rows of the Matrices B_{n}

4. The lower triangles of Twin^{(1)}

5. The lower triangles of Twin^{(2)}

9. The Formal Laplace Transform

References

Key words and phrases. Entringer numbers, tangent and secant numbers, alternating permutations, André permutations, Seidel matrix sequence, increasing binary trees, greater neighbor of maximum, spike, pit, tight permutations, hooked permutations, Seidel triangle sequence, formal Laplace transform.

Mathematics Subject Classifications. 05A15, 05A30, 11B68, 33B10.

1. Introduction

The notion of alternating or zigzag permutation devised by Désiré André, back in 1881 [An1881], for interpreting the coefficients E(n) (n ≥ 0) of the Taylor expansion of tan u + sec u, the so-called tangent and secant numbers, has remained some sort of a curiosity for a long time, until it was realized that the geometry of these alternating permutations could be exploited to obtain further arithmetic refinements of these numbers. Classifying alternating permutations according to the number of inversions directly leads to the constructions of their q-analogs (see [AF80, AG78, St76]). Sorting them according to their first letters led Entringer [En66] to obtain a fruitful refinement E_{n} = ∑_{m} E_{n}(m) that has been described under several forms [OEIS, GHZ11, KPP94, MSY96, St10], the entries E_{n}(m) satisfying a simple finite difference equation (see (1.1) below).

In fact, these numbers E_{n}(m), called Entringer numbers in the sequel, appear in other contexts, in particular when dealing with analytical properties of the André permutations, of the two kinds I and II, introduced by Schützenberger and the first author ([FSch73, FSch71]). For each n ≥ 1 let And_{n}^{I} (respectively And_{n}^{II}) be the set of all André permutations of 12 ⋯ n (see §1.2). It was shown that # And_{n}^{I} = # And_{n}^{II} = E_{n}. The first purpose of this paper is to show that there are several natural statistics “stat,” defined on And_{n}^{I} (respectively And_{n}^{II}), whose distributions are Entringerian, that is, integer-valued mappings “stat,” satisfying

#{w ∈ And_{n}^{I} (respectively And_{n}^{II}) : stat(w) = m} = E_{n}(m).

The second purpose is to work out a matrix refinement E_{n} = ∑_{m,k} a_{n}(m, k) of the tangent and secant numbers, whose row and column sums ∑_{k} a_{n}(m, k) and ∑_{m} a_{n}(m, k) are themselves refinements of the Entringer numbers. This will be achieved, first by inductively defining the so-called twin Seidel matrix sequence (A_{n}, B_{n}) (n ≥ 2) (see §1.5), then by proving that the entries of these matrices provide the joint distributions of pairs of Entringerian statistics defined on André permutations of each kind (Theorem 1.2). See §1.6 for the plan of action.

The third purpose is to obtain analytical expressions for the joint exponential generating functions for pairs of these Entringerian statistics. See §1.7 and the contents of Section 7 and 8. Let us give more details on the notions introduced so far.

1.1. Entringer numbers. 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} = E_{n}, where E_{n} is the tangent number (respectively secant number) when n is odd (respectively even), these numbers appearing in the Taylor expansions of sec u and tan u:

tan u = ∑_{n≥1} \frac{u^{2n−1}}{(2n − 1)!}E_{2n−1} = \frac{u}{1!}1+ \frac{u^{3}}{3!} 2+ \frac{u^{5}}{5!} 16+ \frac{u^{7}}{7!} 272+ \frac{u^{9}}{9!} 7936+⋯,

sec u = ∑_{n≥0} \frac{u^{2n}}{(2n)!}E_{2n} = 1+ \frac{u^{2}}{2!} 1+ \frac{u^{4}}{4!} 5+ \frac{u^{6}}{6!} 61+ \frac{u^{8}}{8!} 1385+ \frac{u^{10}}{10!} 50521+· · · .

(See, e.g., [Ni23, pp. 177–178], [Co74, pp. 258–259]).

Let F w := x_{1} be the first letter of a permutation w = x_{1}x_{2} ⋯ x_{n} of 12 ⋯ n. For each m = 1, …, n, the Entringer numbers are defined by E_{n}(m) := #{w ∈ Alt_{n} : F w = m}, as was introduced by Entringer [En66]. In particular, E_{n}(n) = 0 for n ≥ 2. He showed that these numbers satisfy the recurrence

(1.1)  E_{1}(1) := 1; E_{n}(n) := 0 for all n ≥ 2;
ΔE_{n}(m) + E_{n−1}(n − m) = 0 (n ≥ 2; m = n − 1, …, 2, 1);

where Δ stands for the classical finite difference operator (see, e.g. [Jo39]) ΔE_{n}(m) := E_{n}(m + 1) − E_{n}(m). See Fig. 1.1 for the table of their first values. These numbers are registered as the sequence A008282 in Sloane’s On-Line Encyclopedia of Integer Sequences, together with an abundant bibliography [OEIS]. They naturally constitute a refinement of the tangent and secant numbers:

(1.2)  ∑_{m} E_{n}(m) = E_{n} = \{ \begin{matrix}tangent number, & if n is odd; \\ secant number, & if n is even. \end{matrix}

m = 1 2 3 4 5 6 7 8 9 Sum
n = 1 1  1
2 1 0  1
3 1 1 0  2
4 2 2 1 0  5
5 5 5 4 2 0  16
6 16 16 14 10 5 0  61
7 61 61 56 46 32 16 0  272
8 272 272 256 224 178 122 61 0  1385
9 1385 1385 1324 1202 1024 800 544 272 0 7936

Fig. 1.1. The Entringer Numbers E_{n}(m)

Now, let L w := x_{n} denote the last letter of a permutation w = x_{1}x_{2} ⋯ x_{n} of 12 ⋯ n. In our previous paper [FH14] we made a full study of the so-called Bi-Entringer numbers defined by

E_{n}(m, k) := #{w ∈ Alt_{n} : F w = m, L w = k},

and showed that the sequence of the matrices (E_{n}(m, k)_{1≤m,k≤n}) (n ≥ 1) was fully determined by a partial difference equation system and the three-variable exponential generating function for these matrices could be calculated. As the latter analytical derivation essentially depends on the geometry of alternating permutations, it is natural to ask whether other combinatorial models, counted by tangent and secant numbers, are likely to have a parallel development.

Let E(u) := tan u + sec u = ∑_{n≥0}(u^{n}/n!) E_{n}. Then the first and second derivatives of E(u) are equal to E′(u) = E(u) sec u and E′′(u) = E(u) E′(u), two identities equivalent to the two recurrence relations

(*)  E_{n+1} = ∑_{0≤2j≤n} \binom{n}{2j}E_{n−2j}E_{2j} (n ≥ 0),  E_{0} = 1;

(**) E_{n+2} = ∑_{0≤j≤n} \binom{n}{j}E_{j} E_{n+1−j} (n ≥ 0), E_{0} = E_{1} = 1.

The first of these relations can be readily interpreted in terms of alternating permutations, or in terms of the so-called Jacobi permutations introduced by Viennot [Vi80]. The second one leads naturally to the model of André permutations, whose geometry will appear to be rich and involves several analytic developments.

1.2. André permutations. These permutations were introduced in [FSch73, FSch71], and further studied in [Str74, FSt74, FSt76]. Other properties have been developed in work by Purtill [Pu93], Hetyei [He96], Hetyei and Reiner [HR98], the present authors [FH01], Stanley [St94], in particular in the study of the cd-index in a Boolean algebra. More recently, Disanto [Di14] has been able to calculate the joint distribution of the right-to-left minima and left-to-right minima in these permutations.

In the sequel, permutations of a finite set Y = {y_{1} < y_{2} < ⋯ < y_{n}} of positive integers will be written as words w = x_{1}x_{2} ⋯ x_{n}, where the letters x_{i} are the elements of Y in some order. The minimum (respectively maximum) letter of w, in fact, y_{1} (respectively y_{n}), will be denoted by min(w) (respectively max(w)). When writing w = v min(w) v′ it is meant that the word w is the juxtaposition product of the left factor v, followed by the letter min(w), then by the right factor v′.

Definition. Say that the empty word e and each one-letter word are both André I and André II permutations. Next, if w = x_{1}x_{2} ⋯ x_{n} (n ≥ 2) is a permutation of a set of positive integers Y = {y_{1} < y_{2} < ⋯ < y_{n}}, write w = v min(w) v′. Then, w is said to be an André I (respectively André II) permutation if both v and v′ are themselves André I (respectively André II) permutations, and furthermore if max(vv′) (respectively min(vv′)) is a letter of v′.

The set of all André I (respectively André II) permutations of Y is denoted by And_{Y}^{I} (respectively And_{Y}^{II}), and simply by And_{n}^{I} (respectively And_{n}^{II}) when Y = {1, 2, …, n}. In the sequel, an André I (respectively André II) permutation, with no reference to a set Y, is meant to be an element of And_{n}^{I} (respectively And_{n}^{II}).

Using such an inductive definition, we can immediately see that E_{n} = # And_{n}^{I} = # And_{n}^{II}, the term \binom{n}{j}E_{j} E_{n+1−j} in (∗∗) being the number of all André I (respectively André II) permutations of x_{1}x_{2} ⋯ x_{n+2} such that x_{j} = 1. Further equivalent definitions will be given in the beginning of Section 2. The first André permutations from And_{n}^{I} and And_{n}^{II} are listed in Table 1.2.

André permutations of the first kind:

n = 1: 1; n = 2: 12; n = 3: 123, 213;

n = 4: 1234, 1324, 2314, 2134, 3124;

n = 5: 12345, 12435, 13425, 23415, 13245, 14235, 34125, 24135, 23145, 21345, 41235, 31245, 21435, 32415, 41325, 31425.

André permutations of the second kind:

n = 1: 1; n = 2: 12; n = 3: 123, 312;

n = 4: 1234, 1423, 3412, 4123, 3124;

n = 5: 12345, 12534, 14523, 34512, 15234, 14235, 34125, 45123, 35124, 51234, 41235, 31245, 51423, 53412, 41523, 31524.

Table 1.2: the first André permutations of both kinds

1.3. Statistics on André permutations. The statistics “F ” and “L ” have been previously introduced. Two further ones are now defined: the next-to-last (or the penultimate) letter “NL” and greater neighbor of the maximum “grn”: for w = x_{1}x_{2} ⋯ x_{n} and n ≥ 2 let NL w := x_{n−1}; next, let x_{i} = n for a certain i (1 ≤ i ≤ n) with the convention that x_{0} = x_{n+1} := 0. Then, grn w := max{x_{i−1}, x_{i+1}}.

Let (Ens_{n}) (n ≥ 1) be a sequence of non-empty finite sets and “stat” an integer-valued mapping w ↦ stat(w) defined on each Ens_{n}. The pair (Ens_{n}, stat) is said to be Entringerian, if #Ens_{n} = E_{n} and #{w ∈ Ens_{n} : stat(w) = m} = E_{n}(m) holds for each m = 0, 1, …, n. We also say that “stat” is an Entringerian statistic. The pair (Alt_{n}, F ) is Entringerian, par excellence, for all n ≥ 1.

Theorem 1.1. For each n ≥ 2 the mappings (i) F defined on And_{n}^{I}, (ii) n − NL defined on And_{n}^{I}, (iii) (n + 1) − L defined on And_{n}^{II}, (iv) n − grn defined on And_{n}^{II},

are all Entringerian statistics.

Statements (i) and (ii) will be proved in Section 2 by constructing two bijections η and θ having the property

(1.3)

Alt_{n} ⟶^{η} And_{n}^{I} ⟶^{θ} And_{n}^{I}
w ↦ w′ ↦  w′′
F w = F w′ = (n − NL)w′′

For proving (iii) and (iv) we use the properties of two new bijections ϕ : And_{n}^{I} → And_{n}^{II} and g : And_{n}^{I} → And_{n}^{I}, whose constructions are described in Sections 3 and 4. By means of these two bijections, as well as the bijection θ mentioned in (1.3), it will be shown in Section 5 that the following properties hold:

(1.4) And_{n}^{I} ⟶^{ϕ ∘ g}  And_{n}^{II} w ↦  w′

F w = (n + 1 − L )w′

and

(1.5) And_{n}^{I} ⟶^{ϕ ∘ θ} And_{n}^{II} w ↦  w′′

F w = (n − grn)w′′

thereby completing the proof of Theorem 1.1.

1.4. The fundamental bijection ϕ. For proving (1.4) and (1.5) and also the next Theorem 1.2, two new statistics are to be introduced, the spike “spi” and the pit “pit”, related to the left minimum records for the former one, and the right minimum records for the latter one. In Section 3 the bijection ϕ between And_{n}^{I} and And_{n}^{II} will be shown to have the further property:

(1.6)  (F , spi, NL)w = (pit, L , grn)ϕ(w).

This implies that (1.7) for each pair (m, k) the two sets {w ∈ And_{n}^{I} : (spi, NL)w = (m, k)} and {w ∈ And_{n}^{II} : (L , grn)w = (m, k)} are equipotent.

It also follows from Theorem 1.1 that “(n + 1) − spi” on And_{n}^{I} and “pit” on And_{n}^{II} are two further Entringerian statistics.

1.5. The twin Seidel matrix sequence. The next step is to say something about the joint distributions of the pairs (F , NL) on And_{n}^{I} and (L , grn) on And_{n}^{II}, whose marginal distributions are Entringerian, as announced in Theorem 1.1. We shall proceed in the following way: first, the notion of twin Seidel matrix sequence (A_{n}, B_{n}) (n ≥ 2) will be introduced (see Definition below), then the entry in cell (m, k) of A_{n} (respectively B_{n}) will be shown to be the number of André I (respectively II) permutations w, whose values (F , NL)w (respectively (L , grn)w) are equal to (m, k). The definition involves the partial difference operator Δ_{(1)} acting on

sequences (a_{n}(m, k)) (n ≥ 2) by

Δ_{(1)} a_{n}(m, k) := a_{n}(m + 1, k) − a_{n}(m, k).

The subscript (1) indicates that the difference operator is to be applied to the variable occurring at the first position, which is ‘m’ in the previous equation.

Definition. The twin Seidel matrix sequence (A_{n}, B_{n}) (n ≥ 2) is a sequence of finite square matrices that obey the following five rules (TS1)– (TS5) (see Diagram 1.3 for the values of the first matrices, where zero entries are replaced by dots):

(TS1) each matrix A_{n} = (a_{n}(m, k)) (respectively B_{n} = b_{n}(m, k)) (1 ≤ m, k ≤ n) is a square matrix of dimension n (n ≥ 2) with nonnegative entries, and zero entries along its diagonal, except for a_{2}(1, 1) = 1; let a_{n}(m, •) = ∑_{k} a_{n}(m, k) (respectively a_{n}(•, k) = ∑_{m} a_{n}(m, k)) be the mth row sum (respectively k-th column sum) of the matrix A_{n} with an analogous notation for B_{n};

(TS2) for n ≥ 3 the entries along the rightmost column in both A_{n} and B_{n} are zero, as well as the entries in the bottom row of A_{n} and the top row of B_{n}, i.e., a_{n}(•, n) = b_{n}(•, n) = a_{n}(n, •) = b_{n}(1, •) = 0, as all the entries are supposed to be nonnegative; furthermore, b_{n}(n, 1) = 0;

(TS3) the first two matrices of the sequence are supposed to be:

A_{2} = \begin{matrix}1 & · \\ · & · \end{matrix} , B_{2} = \begin{matrix}· & · \\ 1 & · \end{matrix} ;

(TS4) for each n ≥ 3 the matrix B_{n} is derived from the matrix A_{n−1} by means of a transformation Ψ : (a_{n−1}(m, k)) → (b_{n}(m, k)) defined as follows

(TS4.1)  b_{n}(n, k) := a_{n−1}(•, k − 1) (2 ≤ k ≤ n − 1);
(TS4.2)  b_{n}(n − 1, k) := a_{n−1}(•, k) (2 ≤ k ≤ n − 2);

and, by induction,

(TS4.3) Δ_{(1)} b_{n}(m, k) − a_{n−1}(m, k) = 0 (2 ≤ k + 1 ≤ m ≤ n − 2);
(TS4.4) Δ_{(1)} b_{n}(m, k) − a_{n−1}(m, k − 1) = 0 (3 ≤ m + 2 ≤ k ≤ n − 1);

(TS5) for each n ≥ 3 the matrix A_{n} is derived from the matrix B_{n−1} by means of a transformation Φ : (b_{n−1}(m, k)) → (a_{n}(m, k)) defined as follows

(TS5.1)  a_{n}(1, k) := b_{n−1}(•, k − 1) (2 ≤ k ≤ n − 1);

and, by induction,

(TS5.2) Δ_{(1)} a_{n}(m, k) + b_{n−1}(m, k − 1) = 0 (3 ≤ m + 2 ≤ k ≤ n − 1);
(TS5.3) Δ_{(1)} a_{n}(m, k) + b_{n−1}(m, k) = 0 (2 ≤ k + 1 ≤ m ≤ n − 1).
A_{2} = \begin{matrix}1 & · \\ · & · \end{matrix} ⟶^{Ψ} B_{3} = \begin{matrix}· & · & · \\ 1 & · & · \\ · & 1 & · \end{matrix} ⟶^{Φ} A_{4} = \begin{matrix}· & 1 & 1 & · \\ 1 & · & 1 & · \\ · & 1 & · & · \\ · & · & · & · \end{matrix} ⟶^{Ψ} B_{5} = \begin{matrix}· & · & · & · & · \\ · & · & 1 & 1 & · \\ 1 & 1 & · & 2 & · \\ 1 & 2 & 2 & · & · \\ · & 1 & 2 & 2 & · \end{matrix} ⟶^{Φ}

⟶^{Φ} A_{6} = \begin{matrix}· & 2 & 4 & 5 & 5 & · \\ 2 & · & 4 & 5 & 5 & · \\ 2 & 4 & · & 4 & 4 & · \\ 1 & 3 & 4 & · & 2 & · \\ · & 1 & 2 & 2 & · & · \\ · & · & · & · & · & · \end{matrix} ⟶^{Ψ} B_{7} = \begin{matrix}· & · & · & · & · & · & · \\ · & · & 2 & 4 & 5 & 5 & · \\ 2 & 2 & · & 8 & 10 & 10 & · \\ 4 & 6 & 8 & · & 14 & 14 & · \\ 5 & 9 & 12 & 14 & · & 16 & · \\ 5 & 10 & 14 & 16 & 16 & · & · \\ · & 5 & 10 & 14 & 16 & 16 & · \end{matrix} ⟶^{Φ} A_{8} = \begin{matrix}· & 16 & 32 & 46 & 56 & 61 & 61 & · \\ 16 & · & 32 & 46 & 56 & 61 & 61 & · \\ 16 & 32 & · & 44 & 52 & 56 & 56 & · \\ 14 & 30 & 44 & · & 44 & 46 & 46 & · \\ 10 & 24 & 36 & 44 & · & 32 & 32 & · \\ 5 & 15 & 24 & 30 & 32 & · & 16 & · \\ · & 5 & 10 & 14 & 16 & 16 & · & · \\ · & · & · & · & · & · & · & · \end{matrix}

B_{2} = \begin{matrix}· & · \\ 1 & · \end{matrix} ⟶^{Φ} A_{3} = \begin{matrix}· & 1 & · \\ 1 & · & · \\ · & · & · \end{matrix} ⟶^{Ψ} B_{4} = \begin{matrix}· & · & · & · \\ · & · & 1 & · \\ 1 & 1 & · & · \\ · & 1 & 1 & · \end{matrix} ⟶^{Φ} A_{5} = \begin{matrix}· & 1 & 2 & 2 & · \\ 1 & · & 2 & 2 & · \\ 1 & 2 & · & 1 & · \\ · & 1 & 1 & · & · \\ · & · & · & · & · \end{matrix} ⟶^{Ψ}

⟶^{Ψ} B_{6} = \begin{matrix}· & · & · & · & · & · \\ · & · & 1 & 2 & 2 & · \\ 1 & 1 & · & 4 & 4 & · \\ 2 & 3 & 4 & · & 5 & · \\ 2 & 4 & 5 & 5 & · & · \\ · & 2 & 4 & 5 & 5 & · \end{matrix} ⟶^{Φ} A_{7} = \begin{matrix}· & 5 & 10 & 14 & 16 & 16 & · \\ 5 & · & 10 & 14 & 16 & 16 & · \\ 5 & 10 & · & 13 & 14 & 14 & · \\ 4 & 9 & 13 & · & 10 & 10 & · \\ 2 & 6 & 9 & 10 & · & 5 & · \\ · & 2 & 4 & 5 & 5 & · & · \\ · & · & · & · & · & · & · \end{matrix} ⟶^{Ψ} B_{8} = \begin{matrix}· & · & · & · & · & · & · & · \\ · & · & 5 & 10 & 14 & 16 & 16 & · \\ 5 & 5 & · & 20 & 28 & 32 & 32 & · \\ 10 & 15 & 20 & · & 41 & 46 & 46 & · \\ 14 & 24 & 33 & 41 & · & 56 & 56 & · \\ 16 & 30 & 42 & 51 & 56 & · & 61 & · \\ 16 & 32 & 46 & 56 & 61 & 61 & · & · \\ · & 16 & 32 & 46 & 56 & 61 & 61 & · \end{matrix}

Diagram 1.3: First values of the twin Seidel matrices

It is worth noting that the twin Seidel matrix sequence involves two infinite subsequences: Twin^{(1)} = (A_{2}, B_{3}, A_{4}, B_{5}, A_{6}, …) and Twin^{(2)} = (B_{2}, A_{3}, B_{4}, A_{5}, B_{6}, …). They are independent in the sense that the matrices A_{2n} (respectively B_{2n}) depend only on the matrices B_{2m+1} and A_{2m} (respectively A_{2m+1} and B_{2m}) with m < n, with an analogous statement for the matrices A_{2n+1} (respectively B_{2n+1}).

As is easily verified, Rules (TS1)–(TS5) define the twin Seidel matrix sequence by induction in a unique manner. At each step Rules (TS1) and (TS2) furnish all the zero entries indicated by dots, and Rules (TS4.1), (TS4.2), (TS5.1) the initial values. It remains to use the finite difference equations (TS4.3), (TS4.4), (TS5.2), (TS5.3) to calculate the other entries.

Theorem 1.2. The twin Seidel matrix sequence (A_{n} = (a_{n}(m, k)), B_{n} = (b_{n}(m, k))) (n ≥ 2, 1 ≤ m, k ≤ n) defined by relations (TS1)–(TS5) provides the joint distributions of the pairs (F , NL) on And_{n}^{I} and (L , grn) on And_{n}^{II} in the sense that for n ≥ 2 the following relations hold:

(1.8)  a_{n}(m, k) = #{w ∈ And_{n}^{I} : (F , NL)w = (m, k)};
(1.9)  b_{n}(m, k) = #{w ∈ And_{n}^{II} : (L , grn)w = (m, k)}.

By Theorems 1.1 and 1.2, the row and column sums of the matrices A_{n} and B_{n} have the following interpretations:

(1.10) a_{n}(m, •) = E_{n}(m), b_{n}(m, •) = E_{n}(n + 1 − m), (1 ≤ m ≤ n);
(1.11) a_{n}(•, k) = b_{n}(•, k) = E_{n}(n − k) (1 ≤ k ≤ n);

and furthermore the matrix-analog of the refinement of E_{n} holds:

(1.12)  ∑_{m,k} a_{n}(m, k) = ∑_{m,k} b_{n}(m, k) = E_{n}.

1.6. Tight and hooked permutations. For proving Theorem 1.2, the crucial point is to show that the a_{n}(m, k)’s and b_{n}(m, k)’s satisfy the partial difference equations (TS4.3), (TS4.4), (TS5.2), (TS5.3), when these numbers are defined by the right-hand sides of (1.8) and (1.9). For each pair (m, k) let

A_{n}(m, k) := {w ∈ And_{n}^{I} : (F , NL)w = (m, k)};
B_{n}(m, k) := {w ∈ And_{n}^{I} : (spi, grn)w = (m, k)}.

As the latter set is equinumerous with the set {w ∈ And_{n}^{II} : (L , grn)w = (m, k)} by (1.7), we also have a_{n}(m, k) = #A_{n}(m, k) and b_{n}(m, k) = #B_{n}(m, k), by (1.8) and (1.9).

For the partial difference equation (TS5.2) (respectively (TS5.3)) the plan of action may be described by the diagram

(1.13)

B_{n−1}(m, k − 1) (respectively B_{n−1}(m, k) )
↓ϕ
A_{n}(m, k) = T_{n}(m, k)  ⊎ NT_{n}(m, k)
↓f
A_{n}(m + 1, k)

This means that the set A_{n}(m, k) is to be split into two disjoint subsets, A_{n}(m, k) = T_{n}(m, k) ⊎ NT_{n}(m, k), in such a way that the first component is in bijection with B_{n−1}(m, k − 1) (respectively B_{n−1}(m, k)) by using the bijection ϕ defined in (6.6), and the second one with A_{n}(m + 1, k) by means of the bijection f defined in (6.5). If this plan is realized, the above partial difference equations are satisfied, as

Δ_{(1)} a_{n}(m, k) = #A_{n}(m + 1, k) − #A_{n}(m, k)
= #NT_{n}(m, k) − #A_{n}(m, k)
= −#T_{n}(m, k)
= −#B_{n−1}(m, k − 1) (respectively − #B_{n−1}(m, k)
= −b_{n−1}(m, k − 1) (respectively − b_{n−1}(m, k)).

For the partial difference equation (TS4.3) (respectively (TS4.4)) the corresponding diagram is the following

(1.14)

A_{n−1}(m, k)  (respectively A_{n−1}(m, k − 1 )
↓Θ
B_{n}(m + 1, k) = H_{n}(m + 1, k) ⊎ NH_{n}(m + 1, k)
↑β
B_{n}(m, k)

where Θ and β are two explicit bijections, defined in (6.8) and (6.13), (6.14), respectively. The elements in T_{n}(m, k) from (1.13) (respectively in H_{n}(m + 1, k) from (1.14)) are the so-called tight (respectively hooked) permutations. All details will be given in Section 6 and constitute the bulk of the proof of Theorem 1.2.

1.7. Trivariate generating functions. The final step is to show that the partial difference equation systems (TS4.3), (TS4.4), (TS5.2), (TS5.3) satisfied by the twin Seidel matrix sequence (A_{n}, B_{n}) (n ≥ 2) make it possible to derive closed expressions for the trivariate generating functions for the sequences (A_{2n}), (A_{2n+1}), (B_{2n}), (B_{2n+1}). We list them all in the following theorems. See Section 8 for the detailed proofs.

The calculations are all based on the Seidel triangle sequence technique developed in our previous paper [FH14]. Note that the next generating functions for the matrices A_{n} do not involve the entries of the rightmost columns and bottom rows, which are all zero; they do not involve the entries of the rightmost columns of the matrices B_{n} either, since these are also equal to zero, as assumed in (TS2). Finally, the generating functions for the bottom rows of the matrices B_{n} are calculated separately: see (1.23) and (1.24).

Also, note that the right-hand sides of identities (1.15)–(1.18) are all symmetric with respect to x and z, in agreement with their combinatorial interpretation stated in Theorem 2.4. The property is less obvious for (1.16), but an easy exercise on trigonometry shows that the right-hand

side is equal to the fraction \frac{cos x cos z sin(x + y + z) − sin y}{cos^{2}(x + y + z)} . Finally, the

summations below are taken over triples {(m, k, n)} or pairs {(k, n)} for the last two ones; only the ranges of the summations have been written.

Theorem 1.3 [The sequence (A_{2n}) (n ≥ 1)]. The generating function for the upper triangles is given by

(1.15) ∑_{2≤m+1≤k≤2n−1} a_{2n}(m, k)\frac{x^{m−1}}{(m − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{2n−k−1}}{(2n − k − 1)!}

= \frac{cos x cos z sin(x + y + z)}{cos^{2}(x + y + z)},

and for the lower triangles by

(1.16) ∑_{2≤k+1≤m≤2n−1} a_{2n}(m, k)\frac{x^{2n−m−1}}{(2n − m − 1)!} \frac{y^{m−k−1}}{(m − k − 1)!} \frac{z^{k−1}}{(k − 1)!}

= \frac{cos x sin z}{cos(x + y + z)} + \frac{sin x cos(x + y)}{cos^{2}(x + y + z)}.

Theorem 1.4 [The sequence (A_{2n+1}) (n ≥ 1)]. The generating function for the upper triangles is given by

(1.17) ∑_{2≤m+1≤k≤2n} a_{2n+1}(m, k)\frac{x^{m−1}}{(m − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{2n−k}}{(2n − k)!}

= \frac{cos x cos z}{cos^{2}(x + y + z)},

and for the lower triangles by

(1.18) ∑_{2≤k+1≤m≤2n} a_{2n+1}(m, k)\frac{x^{2n−m}}{(2n − m)!} \frac{y^{m−k−1}}{(m − k − 1)!} \frac{z^{k−1}}{(k − 1)!}

= \frac{cos(x + y) cos(y + z)}{cos^{2}(x + y + z)}.

Theorem 1.5 [The sequence (B_{2n}) (n ≥ 1)]. The generating function for the upper triangles is given by

(1.19) ∑_{2≤m+1≤k≤2n−1} b_{2n}(m, k)\frac{x^{m−1}}{(m − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{2n−1−k}}{(2n − 1 − k)!}

= \frac{sin x cos z}{cos^{2}(x + y + z)},

and for the lower triangles by

(1.20) ∑_{2≤k+1≤m≤2n−1} b_{2n}(m, k)\frac{x^{2n−m−1}}{(2n − m − 1)!} \frac{y^{m−k−1}}{(m − k1)!} \frac{z^{k−1}}{(k − 1)!}

= \frac{cos(x + y) sin(y + z)}{cos^{2}(x + y + z)}.

Theorem 1.6 [The sequence (B_{2n+1}) (n ≥ 1)]. The generating function for the upper triangles is given by

(1.21) ∑_{2≤m+1≤k≤2n} b_{2n+1}(m, k)\frac{x^{m−1}}{(m − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{2n−k}}{(2n − k)!}

= \frac{sin x cos z sin(x + y + z)}{cos^{2}(x + y + z)},

and for the lower triangles by

(1.22) ∑_{2≤k+1≤m≤2n} b_{2n+1}(m, k)\frac{x^{2n−m}}{(2n − m)!} \frac{y^{m−k−1}}{(m − k − 1)!} \frac{z^{k−1}}{(k − 1)!}

= −\frac{sin x sin z}{cos(x + y + z)} + \frac{cos x cos(x + y)}{cos^{2}(x + y + z)}.

The bivariate generating functions for the bottom rows b_{n}(n, k) (k = 1, 2, …) are computed as follows:

(1.23) ∑_{1≤k≤2n−1} b_{2n}(2n, k)\frac{x^{2n−k−1}}{(2n − k − 1)!} \frac{y^{k−1}}{(k − 1)!} = \frac{cos x}{cos(x + y)};

(1.24) ∑_{1≤k≤2n}b_{2n+1}(2n + 1, k)\frac{x^{k−1}}{(k − 1)!} \frac{y^{2n−k}}{(2n − k)!} = \frac{sin x}{cos(x + y)}.

The previous generating functions for the matrices A_{n}, B_{n} will be derived analytically in Section 8, from the sole definition of twin Seidel matrix sequence given in § 1.5, without reference to any combinatorial interpretation. It will be shown in Section 9 that, conversely, the closed expressions thereby obtained provide an analytical proof of identity (1.12) by means of the formal Laplace transform, that is, the fact that the entries of these matrices furnish a refinement of the tangent and secant numbers.

2. From alternating to André permutations of the first kind

Two further equivalent definitions of André permutations of the two kinds will be given (see Definitions 2.1 and 2.2). They were actually introduced in [Str74, FSt74, FSt76]. First, let x be a letter of a permutation w = x_{1}x_{2} ⋯ x_{n} of a set of positive integers Y = {y_{1} < y_{2} < ⋯ < y_{n}}.

The x-factorization of w is defined to be the sequence (w_{1}, w_{2}, x, w_{4}, w_{5}), where

(1) the juxtaposition product w_{1}w_{2}xw_{4}w_{5} is equal to w;

(2) w_{2} is the longest right factor of x_{1}x_{2} ⋯ x_{i−1}, all letters of which are greater than x;

(3) w_{4} is the longest left factor of x_{i+1}x_{i+2} ⋯ x_{n}, all letters of which are greater than x.

Next, say that x is of type I (respectively of type II ) in w, if, whenever the juxtaposition product w_{2}w_{4} is non-empty, its maximum (respectively minimum) letter belongs to w_{4}. Also, say that x is of type I and II, if w_{2} and w_{4} are both empty.

Definition 2.1. A permutation w = x_{1}x_{2} ⋯ x_{n} of Y = {y_{1} < y_{2} < ⋯ < y_{n}} is said to be an André permutation of the first kind (respectively of the second kind) [in short, “w is André I” (respectively “André II ”)], if x_{i} is of type I (respectively of type II) in w for every i = 1, 2, …, n.

Definition 2.2. A permutation w = x_{1}x_{2} ⋯ x_{n} of Y = {y_{1} < y_{2} < ⋯ < y_{n}} is said to be an André permutation of the first kind (respectively of the second kind), if it has no double descent (a factor of the form x_{i−1} > x_{i} > x_{i+1}) and its troughs (factors x_{i−1}x_{i}x_{i+1} satisfying x_{i−1} > x_{i} and x_{i} < x_{i+1}) are all of type I (respectively of type II). By convention, x_{n+1} := 0.

The following notations are being used. If Y = {y_{1} < y_{2} < ⋯ < y_{n}} is a finite set of positive integers, let ρ_{Y} be the increasing bijection of Y onto {1, 2, …, n}. The inverse bijection of ρ_{Y} is denoted by ρ_{Y}^{−1}. If v = y_{i_{1}}y_{i_{2}} ⋯ y_{i_{n}} is a permutation of Y, written as a word, let ρ_{Y} (v) := ρ_{Y} (y_{i_{1}})ρ_{Y} (y_{i_{2}}) ⋯ ρ_{Y} (y_{i_{n}}) = i_{1}i_{2} ⋯ i_{n} be the reduction of the word v, which is then a permutation of 1 2 ⋯ n. When dealing with a given word v, the subscript Y in ρ_{Y} (v) may be omitted, so that ρ(v) = ρ_{Y} (v). In the same way, the subscript Y in each composition product ρ_{Y}^{−1}αρ_{Y} (v) may be omitted, so that ρ^{−1}αρ(v) = ρ_{Y}^{−1}αρ_{Y} (v).

Also, let c be the bijection i ↦ n + 1 − i from {1, 2, …, n} onto itself. Furthermore, if v = y_{i_{1}}y_{i_{2}} ⋯ y_{i_{n}} is a permutation of Y, written as a word, let C(v) := Y and the length of v be |v| = n. Finally, a left maximum record (respectively left minimum record) of v is defined to be a letter of v greater (respectively smaller) than all the letters to its left.

Proposition 2.1. Let n ≥ 2 and w = x_{1}x_{2} ⋯ x_{n} be André I.

(1) In w = v min(w)v′, both factors v and v′ are André I.

(2) If w is from And_{n}^{I}, then both permutations 1 (x_{1}+1) (x_{2}+1) ⋯ (x_{n}+1) and x_{1}x_{2} ⋯ x_{n} (n+1) belong to And_{n+1}^{I}, and (x_{2}−1)(x_{3}−1) ⋯ (x_{n}−1) belongs to And_{n−1}^{I} whenever x_{1} = 1.

(3) The last letter x_{n} is the maximum letter.

(4) Let w = w′ y w′′x_{n} with y being the second greatest letter of w. If w′′ ≠ e, then F w′′ = min(w′′).

(5) For each left maximum record y of v, less than max(w), the two factors uy and u′ in the factorization w = u y u′ are themselves André I.

(6) Let w = v y v′ be André I. If y is a left minimum record, then v is André I.

(7) Let w = v y v′ be an arbitrary permutation with y a letter. If both factors v and y v′ are André I and y is a left minimum record, then w is André I.

Proof. (1) By the very definition given in Subsection 1.2.

(2) Clear.

(3) Write w = v min(w)v′. By definition, max(v′) = max(vv′) = max(w), and by induction the last letter of v′, which is also the last letter of w, is equal to max(v′) = max(w).

(4) If w′′ ≠ e, let x := F w′′, and let (w_{1}, w_{2}, x, w_{4}, w_{5}) be the xfactorization of w. As y is the maximum letter of w_{2}, the maximum letter of w_{4} must be equal to max w to make x of type I. This can be achieved only if x is the minimum of w′′.

(5) Let x := min(w) and y be a left maximum record less than max(w), so that w = v x v′ = u y u′ for some factors v, v′ ≠ e, u, u′ ≠ e. Two cases are to be considered: (i) x to the left of y so that w = v x v′′ y u′; (ii) y to the left of x so that w = u y u′′ x v′ for some factors v′′, u′′. In case (i) both factors v and v′′ y u′ are André I, following the definition in § 2.1. Now, the letter y is also a left maximum record of the word v′′ y u′. By induction on the length, both v′′ y and u′ are André I, so that the two factors v and v′′y of the word u y = v x v′′y are André I, making the latter word also André I. Thus, both uy and u′ are André I. In case (ii), the same argument applies: both factors u y u′′ and v′ are André I, then also u y and u′′ by induction, as well as the juxtaposition product u′′ x v′.

(6) If y = min w, then v is André I by definition. Otherwise, y is to the left of min(w) in {w : w = v y u min(w) u′}. But y is also a left minimum record of v y u. By induction on the length, v is André I.

(7) If y = min(w), then v′ is André I by (2). Now, v and v′ being both André I, the product w = v y v′ is André I by definition. If y > min(w), then w = v y u min(w) u′. There is nothing to prove if v = e. Otherwise, as y v′ is André I, both factors y u and u′ are André I. As y is also a left minimum record of v y u, the juxtaposition product v y u is André I by induction on the length. Finally, w itself is André I by definition, as u′ has been proved to be also André I.

In [FSch71] a bijection between And_{n}^{I} and Alt_{n} was constructed, but did not preserve the first letter. For proving Theorem 1.1(i), we need construct a bijection

(2.1)  η : w → η(w), such that F w = F η(w),

of And_{n}^{I} onto the set Alt_{n} of all alternating permutations of length n. For n = 1, 2, 3 it suffices to take: 1 ↦ 1, 12 ↦ 12, 123 ↦ 132, 213 ↦ 231. When n ≥ 4, each w from And_{n}^{I} can be written w = w′ 1 w′′, where both factors w′, w′′ (with w′ possibly empty) are André I.

If w′ = e, let v′ := 1 and v′′ := ρ^{−1} c η ρ(w′′);

if w′ ≠ e, let

v′ := ρ^{−1} η ρ(w′);
v′′ := \{ \begin{matrix}ρ^{−1} η ρ(1 w′′), & if |w′| is even; \\ ρ^{−1} c η ρ(1 w′′), & if |w′| is odd; \end{matrix}

and

(2.2)  η(w) := v′ v′′.

For instance, let w = 1234 ∈ And_{4}^{I}. Then, w′ = e, w′′ = 234; hence, v′ = 1, ρ(w′′) = 123, η(123) = 132, c(132) = 312, ρ^{−1}(312) = 423 = v′′ and η(1234) = 1423.

With w = 4361257 we get w′ = 436, w′′ = 257; hence, ρ(436) = 213, η(213) = 231, ρ^{−1}(231) = 463 = v′. Also, ρ(1257) = 1234, η(1324) = 1423, c(1423) = 4132, ρ^{−1}(4132) = 7152 = v′′ and η(4361257) = 4637152.

Theorem 2.2. The mapping η defined by (2.2) is a bijection between And_{n}^{I} and Alt_{n} such that F w = F η(w).

Proof. Again, factorize an André I permutation w in the form w = x_{1}x_{2} ⋯ x_{n} = w′1w′′. When w′ = e, then ρ(w′′) is an André I permutation starting with ρ(x_{2}). By induction, η ρ(w′′) is an increasing alternating permutation if |w′′| ≥ 2. Then c η ρ(w′′) will be a falling alternating permutation, as well as the permutation v′′ = ρ^{−1} c η ρ(w′′), which is also a permutation of 23 ⋯ n. Hence, η(v) = 1 v′′ will be an alternating permutation starting with 1.

When w′ ≠ e, then v′ is an alternating permutation of the set C(w′). By induction, it starts with the same letter as the first letter of w, that is, x_{1}. If |w′| is even, v′′ = ρ^{−1} η ρ(1 w′′) is an alternating permutation starting with 1, by induction. The juxtaposition product v′v′′ will then be an alternating permutation starting with x_{1}, as the last letter of v′ is necessarily greater than the first letter of v′′. If |w′| is odd, we just have to verify that L v′ < F v′′. But w, being an André I permutation, ends with its maximum letter n and so does w′′. By induction, η ρ(1 w′′) starts with 1, so that c η ρ(1 w′′) starts with the maximum letter n. Therefore, v′′ is a falling alternating permutation starting with n and v′v′′ is an alternating permutation starting with x_{1}.

For each permutation w = x_{1}x_{2} ⋯ x_{n−1}x_{n} (n ≥ 2) the next-to-last letter NL w of w has been defined as NL w := x_{n−1}. The construction of a bijection θ from And_{n}^{I} onto itself having the property

(2.3) NL θ(w) + F w = |w| = n is quite simple. It suffices to define: (2.4) θ(x_{1} ⋯ x_{n−2}x_{n−1} n) := (n − x_{n−1}) (n − x_{n−2}) ⋯ (n − x_{1}) n.

Property (2.3) is readily seen. It remains to prove that, if w belongs to And_{n}^{I}, so does θ(w). This is the object of the next Proposition.

Proposition 2.3. Let Y = {y_{1} < y_{2} < ⋯ < y_{n}} be a finite set of positive integers and w = x_{1}x_{2} ⋯ x_{n} be an André I permutation from the set And_{Y}^{I}. Then θ(w) := (x_{n} − x_{n−1})(x_{n} − x_{n−2}) ⋯ (x_{n} − x_{1})x_{n} is also André I.

Proof. Proposition 2.3 is true for n = 2, as θ(y_{1}y_{2}) = (y_{2} − y_{1})y_{2}. For n = 3 we have θ(y_{1}y_{2}y_{3}) = (y_{3} − y_{2})(y_{3} − y_{1})y_{3}, θ(y_{2}y_{1}y_{3}) = (y_{3} − y_{1})(y_{3} − y_{2})y_{3}, which are two André I permutations.

For n ≥ 4 let w = x_{1}x_{2} … x_{n} ∈ And_{Y}^{I} be written w = w′y_{1}w′′. If w′ = e, let w′′ − y_{1} := (x_{2} − y_{1}) ⋯ (x_{n−2} − y_{1})(x_{n−1} − y_{1})(y_{n} − y_{1}). Then, w′′ is André I by Lemma 2.1 (b), as well as w′′ −y_{1}, since y_{1} is the smallest element of Y. By induction,

θ(w′′ − y_{1}) = (y_{n} − y_{1} − (x_{n−1} − y_{1})) (y_{n} − y_{1} − (x_{n−2} − y_{1}))
⋯ (y_{n} − y_{1} − (x_{2} − y_{1}))(y_{n} − y_{1})
= (y_{n} − x_{n−1}) (y_{n} − x_{n−2}) ⋯ (y_{n} − x_{2})(y_{n} − y_{1})

is André I. Therefore,

\begin{matrix}(y_{n} − x_{n−1}) (y_{n} − x_{n−2}) ⋯ (y_{n} − x_{2})(y_{n} − y_{1})y_{n} \\ = (x_{n} − x_{n−1}) (x_{n} − x_{n−2}) ⋯ (x_{n} − x_{2})(x_{n} − x_{1})y_{n} \end{matrix}

is André I a fortiori and is precisely the expression of θ(w) that was wanted. Let |w′| = k ≥ 1. By induction, both

θ(w′y_{n}) = (y_{n} − x_{k}) ⋯ (y_{n} − x_{2})(y_{n} − x_{1}) y_{n}

and

θ(y_{1}w′′) = (y_{n} − x_{n−1}) ⋯ (y_{n} − x_{k+2}) (y_{n} − y_{1}) y_{n}

are André I, and also

θ̌(y_{1}w′′) := (y_{n} − x_{n−1}) ⋯ (y_{n} − x_{k+2}) (y_{n} − y_{1}).

The juxtaposition product θ̌(y_{1}w′′) θ_{n}(w′y_{n}) reads

(y_{n} − x_{n−1}) ⋯ (y_{n} − x_{k+2}) (y_{n} − y_{1})(y_{n} − x_{k}) ⋯ (y_{n} − x_{2})(y_{n} − x_{1}) y_{n},

that is, precisely θ(w), since y_{n} − y_{1} = y_{n} − x_{k+1}.

Now, note that x_{k} is the greatest letter of w′ by Lemma 2.1 (3), so that (y_{n} − x_{k}) is the smallest letter of the right factor

(y_{n} − x_{k}) ⋯ (y_{n} − x_{2})(y_{n} − x_{1}) y_{n}

of θ(w). On the other hand, (y_{n}−y_{1}) > (y_{n}−x_{k}). Thus, (y_{n}−x_{k}) is a trough of θ(w); moreover, the (y_{n} − x_{k})-factorization (w_{1}, w_{2}, (y_{n} − x_{k}), w_{4}, w_{5}) of θ(w) is of type I, since w_{2} contains the letter (y_{n} −y_{1}) and w_{4} the letter y_{n}, which is greater than (y_{n} − y_{1}). Finally, the x-factorizations of the other letters x from θ̌(y_{1}w′′) (respectively from θ(w′y_{n})) in each of these two factors are identical with their x-factorizations in θ(w). They are then all of type I, and θ(w) is André I.

By Proposition 2.3 and Identity (2.3) we obtain the following result.

Theorem 2.4. The statistics “F” and “(n − NL)” are both Entringerian on And_{n}^{I}. Moreover, the distribution of the bivariate statistic (F, n − NL) on And_{n}^{I} is symmetric.

3. The bijection ϕ between André I and André II permutations

For each permutation w = x_{1}x_{2} ⋯ x_{n} of 12 ⋯ n (n ≥ 2) make the convention x_{n+1} := 0 and introduce the statistic spike of w, denoted by “spi w,” to be equal to the letter x_{i} (1 ≤ i ≤ n) having the properties

(3.1)  x_{1} ≤ x_{1}, x_{1} ≤ x_{2}, …, x_{1} ≤ x_{i}, and x_{1} > x_{i+1}.

The spike statistic may be regarded as the permutation analog of the classical statistic that measures the time spent by a particle starting at the origin and wandering in the y > 0 part of the xy-plane, before crossing the x-axis for the first time. For instance, spi(253416) = 4, as all the letters to the left of 4 are greater than or equal to 2, but the letter following 4 is less than 2. Also, spi(425136) = 4 and spi(14235) = 5.

When w is an André I permutation and spi w = x_{i}, then x_{i} is a left maximum record, i.e., greater than all the letters to its left. Otherwise, the minimum trough between the maximum letter within x_{1}x_{2} ⋯ x_{i−1} would not be of type I. Accordingly, when w is an André I permutation, the spike x_{i} of w can also be defined as the smallest left maximum record (or the leftmost one), whose successive letter x_{i+1} is less than x_{1}.

For introducing the statistic “pit”, we restrict the definition to all permutations w = x_{1}x_{2} ⋯ x_{n} of 12 ⋯ n such that n ≥ 2 and x_{n−1} < x_{n}. Let 1 = a_{1} < a_{2} < ⋯ < x_{n−1} = a_{k−1} < x_{n} = a_{k} be the increasing sequence of the right minimum records of w, that is to say, the letters which are smaller than all the letters to their right. With the assumption x_{n−1} < x_{n}, there are always two right minimum records to the right of each letter greater than x_{n}. If x_{n} = n (= max w), let pit w := 1 (= min w). Otherwise, let x_{i} be the rightmost letter greater than x_{n} and a_{j} < a_{j+1} be the closest pair of right minimum records to the right of x_{i}. Define pit w := a_{j+1}.

For instance, pit(451236) = 1, as the word ends with the maximum letter 6. In the permutation 614235, the letter 6 is the rightmost letter greater than x_{n} = 5, and 1 < 2 is the closest pair of right minimum records to the right of 6, so that pit(614235) = 2.

An alternate definition for “pit” is the following: if w ends with max w, let pit w = min w. Otherwise, write w = w_{1}(min w)w_{2} and define pit w := pit w_{2}. If w_{2} does not end with the maximum letter, let w_{2} = w_{3}(min w_{2})w_{4} and define pit w_{2} := pit w_{4}, continue the process until finding a right factor w_{2j} ending with its maximum letter to obtain pit w := pit w_{2} = ⋯ = pit w_{2j} = min w_{2j}. For instance, pit(614235) = pit(4235) = 2.

Remember that we have introduced three other statistics, namely “NL” (“next-to-last”), “L ” (“last”), and “grn” (“greater neighbor of the maximum”), and that grn w = NLw whenever w is an André I permutation. Our goal is to prove the next theorem.

Theorem 3.1. The triplets (F , spi, NL) on And_{n}^{I} and (pit, L , grn) on And_{n}^{II} are equidistributed.

Let X = {a_{1} < a_{2} < ⋯ < a_{n}} be a set of positive integers (or any finite totally ordered set), and let And_{X}^{I} (respectively And_{X}^{II}) denote the set of all André I (respectively André II) permutations of X. To prove the previous statement, a bijection

(3.2)  ϕ : And_{X}^{I} → And_{X}^{II}

will be constructed having the property

(3.3)  (F , spi, NL) w = (pit, L , grn) ϕ(w).

When n = 0, let ϕ(e) := e with e the empty word. Let ϕ(a_{1}) := a_{1} for n = 1; ϕ(a_{1}a_{2}) := a_{1}a_{2} for n = 2. For n ≥ 3 each permutation w from And_{X}^{I} has one of the two forms:

(i) w = v_{0} a_{1} v_{1} a_{2} v_{2}; (ii) w = v_{0} a_{2} v_{2} a_{1} v_{1}.

Note that the three factors v_{0}, v_{1}, v_{2} and the product v_{0}a_{2}v_{2} are all André I permutations, and v_{0} is possibly empty. In case (i), v_{1} may be empty, but not v_{2} (which ends with a_{n} greater than a_{2}); in case (ii), v_{2} may be empty, but not v_{1} (which ends with a_{n}). For both cases (i) and (ii), define

(3.4)  ϕ(w) := ϕ(v_{1}) a_{1} ϕ(v_{0} a_{2} v_{2}).

By induction, both factors ϕ(v_{1}) and ϕ(v_{0}a_{2}v_{2}) are André II, as well as ϕ(w), since a_{2} is to the right of a_{1}.

Example. Consider the André I permutation

w = 7 8 {5 \atop v_{0}}6 9 {2 \atop a_{2}} {10 \atop v_{2}} {1 \atop a_{1}} 11 3 {12 \atop v_{1}} 4 13;

we then have:

ϕ(w) =^{(ii)} ϕ(11 3 12 4 13) 1 ϕ(7 8 5 6 9 2 10);
ϕ({11 \atop v_{0}} {3 \atop a_{1}} {12 \atop v_{1}} {4 \atop a_{2}} {13 \atop v_{2}}) =^{(i)} 12 3 ϕ(11 4 13);

ϕ({11 \atop a_{2}} {4 \atop a_{1}} {13 \atop v_{1}}) =^{(ii)} 13 4 11;

ϕ(7 {8 \atop v_{0}} {5 \atop a_{2}} 6 {9 \atop v_{2}} {2 \atop a_{1}} {10 \atop v_{1}}) =^{(ii)} 10 2 ϕ(7 8 5 6 9);

ϕ(7 {8 \atop v_{0}} {5 \atop a_{1}} {6 \atop a_{2}} {9 \atop v_{2}}) =^{(i)} 5 ϕ(7 9 6 9);

ϕ({7 \atop a_{2}} {8 \atop v_{2}} {6 \atop a_{1}} {9 \atop v_{1}}) =^{(ii)} 9 6 ϕ(7 8) = 9 6 7 8;

so that

ϕ(w) = 12 3 13 4 11 1 10 2 5 9 6 7 8.

We can verify that (F , spi, NL) w = (pit, L , grn) ϕ(w) = (7, 8, 4).

With the previous definition of ϕ, we see that the maximum letter a_{n} of X occurs in ϕ(v_{0}a_{2}v_{2}) (respectively in ϕ(v_{1})) when w is of form (i) (respectively of form (ii)). For constructing the inverse ϕ^{−1} of ϕ, this suggests that we start with the factorization

v = w_{0} a_{1} w_{1}

of each permutation v from And_{X}^{II} with #X ≥ 3, after defining ϕ^{−1}(e) := e; ϕ^{−1}(a_{1}) := a_{1} for n = 1; ϕ^{−1}(a_{1}a_{2}) := a_{1}a_{2} for n = 2. As both w_{0}, w_{1} are André II permutations with fewer letters, the images ϕ^{−1}(w_{0}), ϕ^{−1}(w_{1}) are defined by induction. Let v_{1} := ϕ^{−1}(w_{0}). As the minimum letter of w_{1} is a_{2}, define v_{0} and v_{2} to be the factors in ϕ^{−1}(w_{1}) := v_{0} a_{2} v_{2}. Next, let

(3.5)  ϕ^{−1}(v) := \{ \begin{matrix}v_{0} a_{1} v_{1} a_{2} v_{2}, & if a_{n} is a letter of w_{1}; \\ v_{0} a_{2} v_{2} a_{1} v_{1}, & if a_{n} is a letter of w_{0}. \end{matrix}

Lemma 3.2. The André II permutation ϕ(w) ends with its maximum letter if and only if w starts with its minimum letter min w, and then pit ϕ(w) = F w = min w.

Proof. This is obviously true for n = 2. For n ≥ 3, we have w = a_{1}v_{1}a_{2}v_{2} and ϕ(w) = ϕ(v_{1})a_{1}ϕ(a_{2}v_{2}). As a_{2}v_{2} is André I starting with its minimum letter a_{2}, then, by induction, ϕ(a_{2}v_{2}) ends with its maximum letter, which is equal to max w. Hence, pit ϕ(w) = pit(ϕ(v_{1})a_{1}ϕ(a_{2}v_{2})) = a_{1} = F w. For the converse take the notation v = w_{0}a_{1}w_{1} of (3.5). When the maximum letter a_{n} occurs in w_{1}, then ψ(v) = v_{0}a_{1}v_{1}a_{2}v_{2} with v_{1} = ψ(w_{0}) and ψ(w_{1}) = v_{0}a_{2}v_{2}. By assumption, a_{n} occurs at the end of v, hence, at the end of w_{1}. By induction, ψ(w_{1}) = v_{0}a_{2}v_{2} starts with its minimum letter. This can be true only if v_{0} = e. Therefore, ψ(v) = a_{1}v_{1}a_{2}v_{2} and starts with its minimum letter a_{1}.

Theorem 3.3. The mapping ϕ is a bijection between And_{n}^{I} and And_{n}^{II}. Moreover, relation (3.3) holds.

Proof. The bijectivity is proved by the construction of the inverse ϕ^{−1} (see (3.5)). To prove identity (3.3), let w be a André I permutation, either of the form v_{0}a_{1}v_{1}a_{2}v_{2}, or of the form v_{0}a_{2}v_{2}a_{1}v_{1}. In both cases,

spi w = spi v_{0} = spi(v_{0}a_{2}v_{2})
= L ϕ(v_{0}a_{2}v_{2})  [by induction]
= L (ϕ(v_{1})a_{1}ϕ(v_{0}a_{2}v_{2})) = L ϕ(w).

Next, if w = v_{0}a_{1}v_{1}a_{2}v_{2}, then

NL w = NL(v_{0}a_{2}v_{2})
= grn ϕ(v_{0}a_{2}v_{2})  [by induction]
= grn(ϕ(v_{1})a_{1}ϕ(v_{0}a_{2}v_{2})) = grn ϕ(w),

because the maximum letter a_{n} is a letter of v_{2}. If w = v_{0}a_{2}v_{2}a_{1}v_{1}, then a_{1}v_{1} has at least two letters and ends with a_{n}, so that a_{1}v_{1} is André I of form (i). Consequently,

NL w = NL(a_{1}v_{1})
= grn ϕ(a_{1}v_{1})  [by induction]
= grn(ϕ(v_{1})a_{1}ϕ(v_{0}a_{2}v_{2})) = grn ϕ(w).

When w does not start with its minimum letter, then ϕ(w) = ϕ(v_{1})a_{1}ϕ(v_{0}a_{2}v_{2}), and ϕ(v_{0}a_{2}v_{2}) does not end with max w. Therefore, pit ϕ(w) = pit ϕ(v_{0}a_{2}v_{2}) = F v_{0}a_{2}v_{2}. As v_{0} = e only in case (ii), we then have: pit ϕ(w) = F v_{0}a_{2} = F w.

4. The bijection g from the set of André I permutations onto itself

When making up the tables of the distribution of the bivariate statistic (spi, F ) on And_{n}^{I} for n = 1, 2, …, 7, as shown in Table 4.1, it can be noticed that the matrices are symmetric with respect to their skewdiagonals. The property will hold in general if a bijection g from And_{n}^{I} onto itself can be constructed satisfying

(4.1)  (F , spi) w = (n + 1 − spi, n + 1 − F ) g(w)

for all w from And_{n}^{I}.

\begin{matrix}F = & 1 \\ spi = 2 & 1 \\ n = 2 \end{matrix}  \begin{matrix}F = & 1 & 2 \\ spi = 2 & . & 1 \\ 3 & 1 & . \\ n = 3 \end{matrix}  \begin{matrix}F = & 1 & 2 & 3 \\ spi = 2 & . & 1 & . \\ 3 & . & 1 & 1 \\ 4 & 2 & . & . \\ n = 4 \end{matrix}  \begin{matrix}F = & 1 & 2 & 3 & 4 \\ spi = 2 & . & 2 & . & . \\ 3 & . & 1 & 3 & . \\ 4 & . & 2 & 1 & 2 \\ 5 & 5 & . & . & . \\ n = 5 \end{matrix}

\begin{aligned}F = & 1 & 2 & 3 & 4 & 5 \\ spi = 2 & . & 5 & . & . & . \\ 3 & . & 2 & 8 & . & . \\ 4 & . & 3 & 3 & 8 & . \\ 5 & . & 6 & 3 & 2 & 5 \\ 6 & 16 & . & . & . & . \\ & n = 6 \end{aligned}  \begin{aligned}F = & 1 & 2 & 3 & 4 & 5 & 6 \\ spi = 2 & . & 16 & . & . & . & . \\ 3 & . & 5 & 27 & . & . & . \\ 4 & . & 7 & 8 & 31 & . & . \\ 5 & . & 11 & 10 & 8 & 27 & . \\ 6 & . & 22 & 11 & 7 & 5 & 16 \\ 7 & 61 & . & . & . & . & . \\ & & n = 7 \end{aligned}

Table 4.1: distribution of (spi, F ) on And_{n}^{I}

For the construction of g we proceed as follows. An André I permutation v = y_{1}y_{2} ⋯ y_{l} on a set X (of cardinality l ≥ 2) is called simple, if the first letter y_{1} of v is equal to min X. Consider an André I permutation w = x_{1}x_{2} ⋯ x_{n} from And_{n}^{I}. Let 1 = a_{1} < a_{2} < ⋯ < a_{r} (respectively 1 = b_{1} < b_{2} < ⋯ < b_{s} = n) be the increasing sequence of subscripts such that x_{a_{1}} > x_{a_{2}} > ⋯ > x_{a_{r}} (respectively x_{b_{1}} < x_{b_{2}} < ⋯ < x_{b_{s}}) is the increasing (respectively decreasing) sequence of the left minimum (respectively maximum) records of w = x_{1}x_{2} ⋯ x_{n} from And_{n}^{I}.

For the following André I permutation the left minimum (respectively maximum) records are underlined (respectively overlined):

w = \underline{\overline{7}} \overline{8} \underline{5} 6 \overline{9} \underline{2} \overline{10} \underline{1} \overline{11} 3 \overline{12} 4 \overline{13} .

Going back to the general case, let

v_{1} := x_{1} ⋯ x_{a_{2}−1}, v_{2} := x_{a_{2}} ⋯ x_{a_{3}−1}, …, v_{r} := x_{a_{r}} ⋯ x_{n},

so that w is the juxtaposition product v_{1}v_{2} ⋯ v_{r}, and the factors v_{i} are obtained by cutting the word w just before each left minimum record. The factorization (v_{1}, v_{2}, …, v_{r}) is called the canonical factorization of the André I permutation w. Furthermore, the sequence

( (F v_{1}, L v_{1}), (F v_{2}, L v_{2}), …, (F v_{r}, L v_{r}) ),

which is also equal to ( (x_{1}, x_{a_{2}−1}), (x_{a_{2}}, x_{a_{3}−1}), …, (x_{a_{r},}x_{n}) ), is called the type of the canonical factorization of w.

In our running example, the canonical factorization reads

w = \underline{\overline{7}} \overline{8} | \underline{5} 6 \overline{9} | \underline{2} \overline{10} | \underline{1} \overline{11} 3 \overline{12} 4 \overline{13}
v_{1} v_{2}  v_{3}  v_{4}

and is of type ( (7, 8), (5, 9), (2, 10), (1, 13) ).

Proposition 4.1. Let (v_{1}, v_{2}, …, v_{r}) be the canonical factorization of the André I permutation w = x_{1}x_{2} ⋯ x_{n} from And_{n}^{I}. Let s be the number of left maximum records of w. Then:

(i) r ≤ s; (ii) each factor v_{i} (i = 1, 2, …, r) is a simple André I permutation; (iii) L v_{i} is a left maximum record, so that L v_{1} < L v_{2} < ⋯ < L v_{r−1} < L v_{r} = n and, of course, F v_{1} > F v_{2} > ⋯ > F v_{r−1} > F v_{r} = 1; (iv) (F v_{1}, L v_{1}) = (F w, spi w).

Let w = x_{1}x_{2} ⋯ x_{n} be an André I permutation from And_{n}^{I} and \overline{w} := \overline{x}_{n}\overline{x}_{n−1}\overline{x}_{n−2} ⋯ \overline{x}_{1} be the permutation defined by \overline{x}_{i} := N − x_{n+1−i} (i = 1, 2, …, n), where N is some integer greater than n.

Proposition 4.2. If w is a simple André I permutation, so is \overline{w}.

For constructing the bijection g, let n ≥ 3 and N := n + 1. If (v_{1}, v_{2}, …, v_{r}) is the canonical factorization of a permutation w from And_{n}^{I}, define g(w) to be the juxtaposition product

(4.1)  g(w) := \overline{v}_{1} \overline{v}_{2} … \overline{v}_{r}.

Furthermore, if τ = ((p_{1}, q_{1}), (p_{2}, q_{2}), …, (p_{r}, q_{r})) is the canonical factorization type of w, let

\overline{τ} := ((\overline{q}_{1}, \overline{p}_{1}), (\overline{q}_{2}, \overline{p}_{2}), …, (\overline{q}_{r}, \overline{p}_{r})).

We then have the following fundamental property of g.

Theorem 4.3. The transformation g is a bijection from And_{n}^{I} onto itself. Furthermore, if τ is the canonical factorization type of w, then \overline{τ} is the canonical factorization type of g(w). In particular,

(4.2)  (F , spi) g(w) = (n + 1 − spi, n + 1 − F ) w.

In the running example, where n + 1 = 14, we get

g(w) = 6 7 | 5 8 9 | 4 12 | 1 10 2 11 3 13,

which is of type ( (6, 7), (5, 9), (4, 12), (1, 13) ).

The proofs of Propositions 4.1, 4.2 and Theorem 4.3 do not present any difficulties and are therefore omitted.

5. The proof of Theorem 1.1 (iii) and (iv)

We reproduce the sequence (1.5) by decomposing the product ϕ ∘ g:

(5.1)

And_{n}^{I} ⟶^{g}  And_{n}^{I}  ⟶^{ϕ}  And_{n}^{II}
w ↦  g(w)  ↦  ϕ(g(w))
F w = n + 1 − spi g(w) = n + 1 − L ϕ(g(w))

The first (respectively second) identity F w = n+1−spi g(w) (respectively spi g(w) = L ϕ(g(w))) is a specialization of (4.2) (respectively of (3.3)).

Take the example of the previous section: w = 7 8 5 6 9 2 10 1 11 3 12 4 13 and g(w) = 6 7 5 8 9 4 12 1 10 2 11 3 13. By using the definition of ϕ given in (3.4), we get ϕ(g(w)) = 10 1 11 2 13 3 12 4 8 9 5 6 7, which belongs to And_{13}^{II}, and n + 1 − L ϕ(g(w)) = 14 − 7 = 7 = F w.

Next, reproduce the sequence (1.4) by decomposing the product ϕ ∘ θ:

(5.2)

And_{n}^{I} ⟶^{θ} And_{n}^{I}  ⟶^{ϕ}  And_{n}^{II}
w ↦  θ(w)  ↦  ϕ(θ(w))
F w = n − NL θ(w) = n − grn ϕ(θ(w))

The first (respectively second) identity F w = n − NL θ(w) (respectively NL θ(w) = grn(ϕ(g(w))) is a specialization of (2.3) (respectively of (3.3)).

For example, with w′ = 10 2 11 3 12 1 9 4 5 8 6 7 13, we obtain θ(w′) = 6 7 5 8 9 4 12 1 10 2 11 3 13 and ϕ(θ(w′)) = 10 1 11 2 13 3 12 4 8 9 5 6 7. Thus, F w′ = 10 = n − NL θ(w′) = 13 − 3 = n − grn ϕ(θ(w′)).

The proofs of (iii) and (iv) of Theorem 1.1 are now completed. Another proof of Theorem 1.1 (iii) and (iv) makes use of the properties of a rearrangement group G_{n}, acting on the group 𝔖_{n} of all permutations of {1, 2, …, n}, which were developed in [FSt74, FSt76], and another correspondence Γ on binary increasing trees, introduced in [FH13]. They constitute the main ingredients for the constructions of three bijections, \overline{Γ}, Φ^{I}, and Φ^{II}, appearing in the diagram

And_{n}^{II} \underrightarrow{\overline{Γ}} 𝔖_{n}/G_{n} \underrightarrow{Φ^{I}} And_{n}^{I}
↓Φ^{II}
And_{n}^{II}

which have the property L w = 1 + NL Φ^{I} \overline{Γ}(w) = 1 + grn Φ^{II} \overline{Γ}(w).

6. Combinatorics of the twin Seidel matrix sequence

This section is devoted to proving Theorem 1.2. As announced in Subsection 1.5, the question is to show that the integers a_{n}(m, k) and b_{n}(m, k), when taken as a_{n}(m, k) = #A_{n}(m, k), b_{n}(m, k) = #B_{n}(m, k) with

(6.1)  A_{n}(m, k) := {w ∈ And_{n}^{I} : (F , NL)w = (m, k)};
(6.2)  B_{n}(m, k) := {w ∈ And_{n}^{I} : (spi, grn)w = (m, k)};

satisfy all the properties (TS1)–(TS5) stated in Subsection 1.5.

The verifications of properties (TS1), (TS2), (TS3), (TS4.1), (TS4.2), (TS5.1) are easy and given in the next subsection. The proofs of the other properties are much harder and will be developed thereafter.

6.1. The first evaluations. By (1.7), the set B_{n}(m, k) is equinumerous with

(6.3)  B′_{n}(m, k) := {w ∈ And_{n}^{II} : (L , grn)w = (m, k)}.

The evaluations in this subsection are made by using B′_{n}(m, k) instead of B_{n}(m, k).

(TS1) Nothing to prove, except for the diagonals of the twin Seidel matrices A_{n} and B_{n}. They have zero entries when n ≥ 3, because the first and next-to-last letter of each André I permutation cannot be the same! On the other hand, the identity L w = grn w = m would mean that the permutation w from And_{n}^{II} ends with a double descent n > m > 0.

(TS2) We have a_{n}(k, n) = b_{n}(k, n) = 0, because grn w ≤ n − 1 for each w from either And_{n}^{I}, or And_{n}^{II}. Also, a_{n}(n, k) = 0, as each permutation from And_{n}^{I} ends with n. Finally, b_{n}(1, k) = 0, because each permutation from And_{n}^{II} cannot end with the letter 1.

(TS3) We have: A_{2} = \begin{matrix}1 & · \\ · & · \end{matrix} and B_{1} = \begin{matrix}· & · \\ 1 & · \end{matrix}, because And_{2}^{I} = And_{2}^{II} = \{12\}

and (F , NL, L , grn)(12) = (1, 1, 2, 1).

(TS4.1) The entry b_{n}(n, k) counts the André II permutations w from And_{n}^{II} ending with the two-letter factor k n. The deletion of the ending letter n maps w onto an André II permutation w′ from And_{n−1}^{II} ending with k in a bijective manner. Hence, b_{n}(n, k) = b_{n−1}(k, •), which is equal to a_{n−1}(•, k − 1) by Theorem 1.1 for 1 ≤ k ≤ n − 1.

(TS4.2) The entry b_{n}(n − 1, k) counts the André II permutations w from And_{n}^{II} of the form w = x_{1} ⋯ x_{i−2} n x_{i} ⋯ x_{n−1} (n − 1) with i ≤ n − 1 and k equal to x_{i−2} or x_{i}. Such a permutation can be mapped onto a permutation w′ from And_{n−1}^{II} defined by

(6.4)  w′ := x_{1} ⋯ x_{i−2} (n − 1) x_{i} ⋯ x_{n−1}.

This defines a bijection between the set of all w from And_{n}^{II} such that (L , grn)w = (n − 1, k) and the set of all w′ from And_{n−1}^{II} such that grn w′ = k (1 ≤ k ≤ n − 2). Thus, b_{n}(n − 1, k) = b_{n−1}(•, k), which is also equal to a_{n}(•, k) by Theorem 1.1.

(TS5.1) The entry a_{n}(1,k) counts the permutations w from A_{n}^{I} such that (F , NL)w = (1, k). The bijection 1 x_{2} ⋯ k n ↦ (x_{2} − 1) ⋯ (k − 1) (n − 1) maps the set of these permutations onto the set of all w′ from A_{n−1}^{I} such that grn w′ = k − 1. Hence, a_{n}(1, k) = a_{n−1}(•, k − 1).

6.2. Tight André I permutations. As sketched in Subsection 1.6 and its display (1.13), proving (TS5.2) and (TS5.3) amounts to do the following points:

(a) split each set A_{n}(m, k) into two disjoint subsets

A_{n}(m, k) = T_{n}(m, k) ⊎ NT_{n}(m, k),

in such a way that (b) when 2 ≤ k + 1 ≤ m ≤ n − 2 or 3 ≤ m + 2 ≤ k ≤ n − 1 a bijection

f : NT_{n}(m, k) → A_{n}(m + 1, k);

(c) and another bijection

ϕ : B_{n−1}(m, k) → T_{n}(m, k),  when m > k;
ϕ : B_{n−1}(m, k − 1) → T_{n}(m, k),  when m < k;

can be duly constructed.

Points (a) and (b). Let f be the transposition of the first letter F w = m within a permutation w and the letter equal to (m+1) (1 ≤ m ≤ n−2):

(6.5)  f : w = m v (m + 1) v′ ↦ w′ = (m + 1) v m v′.

If w is an André I permutation, the image w′ = f(w) is not always an André I permutation. For example, 423516 belongs to And_{6}^{I}, but not f(w) = 523416, for the trough 2 is not of type I. However, the reverse transposition

f^{−1} : w′ = (m + 1) v m v′ ↦ f^{−1}(w′) = w = m v (m + 1) v′,

whenever defined, maps each André I permutation to an André I permutation. The André I permutations w, whose images f(w) are not André I permutations, are called tight. They are characterized as follows.

Definition 6.1. An André I permutation w = m v (m + 1) v′ is said to be tight, if the following two conditions hold:

(i) either v = e, or v ≠ e and all its letters are less than m;

(ii) either v′ ≠ e and F v′ is less than all the letters of w to its left, or v′ = e and necessarily m = n − 1.

Let T_{n} (respectively NT_{n}) be the subset of all André I permutations from And_{n}^{I}, which are tight (respectively not tight), and let T_{n}(m, k) := T_{n} ∩ A_{n}(m, k), NT_{n}(m, k) := NT_{n} ∩ A_{n}(m, k).

Note that the André I permutations from A_{n}(1, k) are all of the form 1 v 2 v′ and, either the letters of v are all greater than 2, or v′ ≠ e but 2 < F v′, so that at least one of conditions (i), (ii) does not hold. Accordingly, NT_{n}(1, k) = A_{n}(1, k) for all k, that is, all André I permutations starting with 1 are not tight. Also, note that each André I permutation from A_{n}(n − 1, k) is of the form w = (n − 1) v n and is necessarily tight, so that T_{n}(n − 1, k) = A_{n}(n − 1, k) for all k.

Proposition 6.1. Let n ≥ 3 and let w be a tight André I permutation from And_{n}^{I}. Then, f(w) (defined in (6.5)) cannot be an André I permutation.

Proof. Take the notation of (6.5) for w and w′ = f(w). If m = n−1, then w′ = n v (n−1) is not André I. If m ≤ n−2, v = e, and (ii) of Definition 6.1 holds, then w′ contains the double descent (m + 1) > m > F v′, therefore is not André I. If m ≤ n − 2, v ≠ e and (ii) of Definition 6.1 holds, let x be the minimum trough in w′ between (m+1) and m; then the x-factorization (w_{1}, w_{2}, x, w_{4}, w_{5}) of w′ is such that max w_{2}w_{4} = m + 1 with (m + 1) a letter of w_{2}. Again, w′ cannot be an André I permutation.

Proposition 6.2. If 2 ≤ k + 1 ≤ m ≤ n − 2 or 3 ≤ m + 2 ≤ k ≤ n − 1, then f maps NT_{n}(m, k) onto A_{n}(m + 1, k) in a bijective manner.

Proof. To prove that w′ is André I when w is not tight, we prove that (i) w′ has no double descent; (ii) all the troughs of w′ are of type I.

(i) The only double descent that could be created when going from w to w′ is (m + 1) > m > F v′. This could occur only if v = e, v′ ≠ e and m > F v′, and this would mean that w is tight; a contradiction.

(ii) Let x_{i} (respectively x′_{i}) be the i-th letter counted from left to right of w (respectively w′). Also, let (w_{1}, w_{2}, x_{i}, w_{4}, w_{5}) (respectively (w′_{1}, w′_{2}, x′_{i}, w′_{4}, w′_{5})) be the x_{i}- (respectively x′_{i}-)factorization of w (respectively of w′). Several cases are to be considered.

(1) Suppose that x_{i} is to the right of (m + 1) in w. Then x′_{i} = x_{i}. If x_{i} is a trough of w, then either (m + 1) is a letter of w_{2}, or not. If it is, then w′_{2} is derived from w_{2} by replacing the letter (m+1) by m. Therefore, max w′_{2} ≤ max w_{2} < max w_{4} = max w′_{4}, and the x′_{i}-factorization remains of type I in w′. If it is not, then w′_{2} = w_{2}, w′_{4} = w_{4}, and the same conclusion holds.

(2) Now, suppose that x_{i} = (m + 1), so that x′_{i} = m. If x_{i} is a trough of w — this is possible, as w is supposed to be not tight — then v ≠ e, and m is not a letter of w_{2}. Furthermore, (m+1) is a letter of w′_{2} only when all the letters between m and (m + 1) are greater than (m + 1). Whatever the particular case may be, we have max w′_{2} = max w_{2} < max w_{4} = max w′_{4}, so that x′_{i} is a trough of type I in w′.

(3) Next, let x_{i} lie between m and (m + 1) in w, so that x′_{i} = x_{i}, and suppose that x_{i} is trough of w. If x_{i} is greater than (m + 1), then w′_{2} = w_{2} and w′_{4} = w_{4}. Moreover, x′_{i} = x_{i} will be a trough of type I in w′. If x_{i} is less than m, the only problem arises when m and (m + 1) are the maximum letters of w_{2} and w_{4}, respectively. In such a case, all the letters between m and (m + 1) are smaller than m and m > F v′. Hence, w would be tight, a contradiction.

Thus, the image f(w) of w, supposed to be not tight, is André I. If 2 ≤ k +1 ≤ m ≤ n−2, a fortiori, k < m+1, so that the next-to-last letter of a permutation w from NT_{n}(m, k), which is equal to k, cannot be equal to (m + 1). Thus, f(NT_{n}(m, k)) ⊂ A_{n}(m + 1, k). In the same manner, if 3 ≤ m+1 < k ≤ n−1, the inequality m+1 < k implies the same inclusion. As f and f^{−1} are inverses of each other when applied to the sets A_{n}(m, k) and A_{n}(m + 1, k), respectively, the restriction of f^{−1} to A_{n}(m + 1, k) is necessarily NT_{n}(m, k) by Proposition 6.1. Thus, Proposition 6.2 is proved for 2 ≤ k + 1 ≤ m ≤ n − 2 and 3 ≤ m + 1 < k ≤ n − 1.

In Table 6.1 the bijection f : NT_{5}(m, k) → A_{5}(m + 1, k) is materialized by the vertical arrows. The five tight permutations in And_{5}^{I} are reproduced in boldface. They can only be targets of these arrows. This completes the program of points (a) and (b).

[figure: 1; 2; 3; 4; NL; F; 1; 2; 3; 4; 13425; 12435; 14235; 12345; 13245; 23415; 21435; 24135; 21345; 23145; 32415; 31245; 31425; 34125; 41325; 41235]

Table 6.1: the bijection f : NT_{5}(m, k) → A_{5}(m + 1, k) (k ≠ m + 1). f : A_{5}(m, m + 1) → A_{5}(m + 1, m)

Remark. When 3 ≤ m + 1 = k ≤ n − 2, in the permutation w = m v (m+1) v′ from A_{n}(m, m+1) the right factor v′ is equal to the oneletter word n. This implies that f maps A_{n}(m, m + 1) onto A_{n}(m + 1, m) in a bijective manner. In particular, a_{n}(m, m + 1) = a_{n}(m + 1, m). This fact is illustrated in Table 6.1 by oblique arrows.

Point (c). Let n ≥ 3, and consider a permutation w = x_{1}x_{2} ⋯ x_{n−1} from And_{n−1}^{I}. Let x_{j} = spi w. Define ϕ(w) := x_{j}x′_{1}x′_{2} ⋯ x′_{n−1}, where

(6.6)  x′_{i} := \{ \begin{matrix}x_{i}, & if x_{i} ≤ x_{j} − 1; \\ x_{i} + 1, & if x_{i} ≥ x_{j}. \end{matrix}

The inverse bijection ϕ^{−1} is defined as follows: let w′ = x′_{1}x′_{2} ⋯ x′_{n} belong to T_{n}; then ϕ^{−1}(w′) := ρ(x′_{2} ⋯ x′_{n}), where ρ is the reduction defined in Section 2.

Theorem 6.3. The mapping ϕ is a bijection between And_{n−1}^{I} and the set T_{n} of all tight André I permutations having the following properties:

(i) spi w = F ϕ(w);

(ii) grn ϕ(w) = \{ \begin{matrix}grn w, & if spi w > grn w; \\ grn w + 1, & if spi w < grn w. \end{matrix}

k =  1  2  3  4  5
m = 1  ·  ·  ·  ·  ·
2  ˆ21435  ˆ21345
231546  231456
3  ˆ32415  ˆ31425  2ˆ3145
342516  341526  324156

ˆ31245 341256

4  23ˆ415  3ˆ4125  2ˆ4135
423516  435126  425136
ˆ41325  ˆ41235
451326  451236
5  1342ˆ5  1243ˆ5  1234ˆ5
513426  512436  512346
1423ˆ5  1324ˆ5
514236  513246

Table 6.2: The bijection ϕ : B_{5}(m, k − 1) (respectively B_{5}(m, k)) → T_{6}(m, k).

In Table 6.2 the permutations in boldface are the elements of And_{5}^{I}. Their images under ϕ are the sixteen tight permutations from T_{6}, written in plain below them. The box (m, k) contains the permutations w from And_{5}^{I} such that spi w = m and grn w = k (respectively grn w = k − 1) when m > k (respectively when m < k). It also contains the elements w′ from T_{6} such that F w′ = m and grn w′ = k. A hat sign has been put on the spike of w.

Proof of Theorem 6.3. Let w = x_{1}x_{2} ⋯ x_{n−2}x_{n−1} be from And_{n−1}^{I}. Let x_{j} = spi w. If j = 1, then x_{1} > x_{2} and ϕ(w) = x_{1} (x_{1} + 1) x_{2} ⋯ x′_{n−2}x′_{n−1}. Accordingly, ϕ(w) is tight. Moreover, spi w = x_{1} = F ϕ(w), still since x_{1} > x_{2}. Also, either grn w = x_{n−2} < x_{1} = spi w, and then grn ϕ(w) = x′_{n−2} = x_{n−2} = grn w, or grn w = x_{n−2} > x_{1} = spi w, and then grn ϕ(w) = x′_{n−2} = x_{n−2} + 1 = grn w + 1.

If j ≥ 2, we have

(6.7)  ϕ(w) = x_{j} x_{1} ⋯ x_{j−1} (x_{j} + 1) x_{j+1} x′_{j+2} ⋯ x′_{n−1}.

On the other hand, ϕ(w) is André I, because no double descent has been created; furthermore, the new trough x_{1} is of type I, as the letter (x_{j} + 1) is to its right. Also, ϕ(w) is tight, because x_{j+1} (respectively (x_{j} + 1)) is less (respectively greater) than all the letters to its left. Finally, spi w = x_{j} = F ϕ(w). Moreover, grn ϕ(w) = x′_{n−2} is equal to x_{n−2} = grn w or x_{n−2} + 1 = grn w + 1, depending on whether x_{n−2} = grn w is less than or at least equal to x_{n} = spi w.

This achieves the program of point (c), by definition of B_{n}(m, k) given in (6.2).

6.3. Hooked and unhooked permutations. Let n ≥ 3, and consider the mapping Θ, defined on And_{n−1}^{I} as follows. Let w = x_{1}x_{2} ⋯ x_{n−1} belong to And_{n−1}^{I}. Define

(6.8)  Θ(w) := \{ \begin{matrix}(x_{1} + 1)x_{1}x′_{2} ⋯ x′_{n−1}, & if x_{1} < x_{2}; \\ x_{1}(x_{1} + 1)x′_{2} ⋯ x′_{n−1}, & if x_{1} > x_{2}; \end{matrix}

where x′_{i} := x_{i} (respectively x_{i} + 1) if x_{i} < x_{1} (respectively if x_{i} > x_{1}). Clearly, Θ is an injection from And_{n−1}^{I} into And_{n}^{I}. The permutations belonging to the subset Θ(And_{n−1}^{I}) are said to be hooked. Their formal definition is stated next.

Definition 6.2. An André I permutation w = x_{1}x_{2} ⋯ x_{n} (n ≥ 3) from And_{n}^{I} is called hooked, if x_{1} − 1 = x_{2} < x_{3} or x_{1} + 1 = x_{2} > x_{3}.

Let H_{n} denote the subset of all the hooked permutations from And_{n}^{I}. The elements of the set-theoretic difference NH_{n} := And_{n}^{I} \H_{n} are said to be unhooked. Let H_{n}(m, k) (respectively NH_{n}(m, k)) denote the subset of H_{n} (respectively of NH_{n}) consisting of all w such that (spi, grn)w = (m, k).

Proposition 6.4. The injection Θ defined in (6.8) from And_{n−1}^{I} into And_{n}^{I} maps And_{n−1}^{I} onto H_{n}. Moreover, for each w from And_{n}^{I} we have

spi Θ(w) = 1 + F w;
(6.9)  grn Θ(w) = \{ \begin{matrix}1 + grn w, & if F w < grn w; \\ grn w, & if F w > grn w. \end{matrix}

Proof. With the notation of (6.8), we have spi Θ(w) = x_{1} + 1 in both cases. The identity for “grn” follows from the very definition of Θ.

Corollary 6.5. The mapping Θ is a bijection between A_{n−1}(m, k) and H_{n}(m + 1, k) when 1 ≤ k < m ≤ n − 2, and onto H_{n}(m + 1, k + 1) when 3 ≤ m + 2 ≤ k ≤ n − 1.

In Table 6.3, the sixteen permutations from And_{5}^{I} are reproduced in boldface, and below them the hooked permutations from H_{6} that are their images under Θ. A hat sign has been put on the spike of each permutation from H_{6}.

k =  1  2  3  4  5
m = 1  ·  ·  ·  ·  ·
2  13425  12435  12345
ˆ214536  ˆ213546  ˆ213456
14235  13245
ˆ215346  ˆ214356
3  23415  21435  21345
ˆ324516  2ˆ31546  2ˆ31456
24135  23145
ˆ325146  ˆ324156
4  32415  31425  31245
3ˆ42516  3ˆ41526  3ˆ41256

34125 ˆ435126

5 41325 41235
4ˆ51326  4ˆ51236

Table 6.3:

the bijection Θ : A_{5}(m, k) → H_{6}(m + 1, k) (respectively H_{6}(m + 1, k + 1))

Referring to the program displayed in (1.14), the first bijection Θ has been constructed. The next step is devoted to the construction of the bijection β.

6.4. A bijection between B_{n}(m, k) and NH_{n}(m + 1, k). We go back to the proofs of (TS4.1) and (TS4.2) made in Subsection 6.1. It was shown that b_{n}(n − 1, k) = b_{n}(n, k + 1) = b_{n−1}(•, k) for 1 ≤ k ≤ n − 2. By means of the bijections described in Subsection 6.1 and Section 4, and also the bijection ϕ constructed in (5.2), we can set up a bijection between B_{n}(n − 1, k) and B_{n}(n, k + 1). We can also proceed directly as follows. Let n ≥ 3 and w = x_{1} ⋯ x_{i−1} ˆ (n − 1) x_{i+1} ⋯ k n be an André I permutation such that (spi, grn)w = (n − 1, k). Then the mapping α defined by

(6.10)  α(w) := 1 (x_{1} + 1) ⋯ (x_{i−1} + 1) (x_{i+1} + 1) ⋯ (k + 1) n̂

fulfills our requirements.

The inverse α^{−1} is easy to find: let w′ = x′_{1} x′_{2} ⋯ x′_{n−1} n be a permutation from B_{n}(n, k + 1), so that x′_{1} = 1. Then α^{−1}(w′) is obtained by first determining the leftmost letter x′_{i+1} less than or equal to x′_{2} and subsequently letting

(6.11) α^{−1}(w′) := (x′_{2} − 1) ⋯ (x′_{i−1} − 1) (n − 1) (x′_{i+1} − 1) ⋯ k n.

The bijection α will be an ingredient for the next bijection, β, between B_{n}(m, k) and NH_{n}(m + 1, k).

First, let

(6.12)  2 ≤ k + 1 ≤ m ≤ n − 2 or 3 ≤ m + 2 ≤ k ≤ n − 1,

and partition B_{n}(m, k) into two subsets B_{n}^{(1)}(m, k), B_{n}^{(2)}(m, k) as follows. Note that each permutation w from B_{n}(m, k) is of the form w = w_{1}mw_{2}(m+1)w_{3} and the factor w_{2} is never empty, as m is the spike of w. Also, w_{3} ≠ e because of condition (6.12). Say that an element of B_{n}(m, k) belongs to B_{n}^{(1)}(m, k) (respectively to B_{n}^{(2)}(m, k)) if F w_{3} is not (respectively if F w_{3} is) a left minimum record, or equivalently, if min w_{2} < F w_{3} (respectively if min w_{2} > F w_{3}).

Let w = x_{1}x_{2} ⋯ x_{n} = w_{1} m w_{2} (m+1) w_{3} be from B_{n}(m, k) with (m, k) satisfying (6.12).

(1) If w belongs to B_{n}^{(1)}(m, k), define w′ := β(w) to be the permutation derived from w by transposing the letters m and (m + 1):

(6.13)  β : w = w_{1} m w_{2} (m + 1) w_{3} ↦ w′ = w_{1} (m + 1) w_{2} m w_{3}.

(2) If w belongs to B_{n}^{(2)}(m, k), consider the factorization w = v_{1}w_{3}, where v_{1} = w_{1} m w_{2} (m + 1). Then v_{1} is André I by Proposition 2.1 (6). Let n′ be the length of v_{1} and ρ(v_{1}) be the reduction of v_{1} (by using the increasing bijection from the set {x_{1}, …, m, …, m+1} onto {1, 2, …, n′}). Thus, ρ(v_{1}) is an André I permutation from And_{n′}^{I} such that spi ρ(v_{1}) = n′ − 1. The bijection α, introduced in (6.10), can be applied to ρ(v_{1}), and the permutation w′ := β(w) is defined by replacing the left factor v_{1} of w by ρ^{−1}αρ(v_{1}):

(6.14)  β : w = v_{1}w_{3} ↦ w′ := ρ^{−1}αρ(v_{1}) w_{3}.

Example. The permutation w = 4 5 3 8 1 6 7 2 9 belongs to B_{9}^{(1)}(5, 2), as min w_{2} = min 381 = 1 < 7 = F w_{3}. It then suffices to transpose 5 and 6 to get the permutation w′ = 4 6 3 8 1 5 7 2 9.

Next, w = 3 5 6 2 7 1 8 4 9 belongs to B_{9}^{(2)}(6, 4), as min w_{2} = 2 > 1 = F w_{3}. Hence, v_{1} = 3 5 6 2 7, ρ(v_{1}) = 2 3 4 1 5, αρ(v_{1}) = 1 3 4 2 5, ρ^{−1}αρ(v_{1}) = 2 5 6 3 7 and w′ = 2 5 6 3 7 1 8 4 9.

When w belongs to B_{n}^{(1)}(m, k), the letter (m + 1) occurs to the left of m in w′. On the other hand, as w_{2} is non-empty and m + 1 > F w_{2}, the permutation w′ is unhooked if w_{1} = e. The same conclusion also holds if w_{1} ≠ e, because L w_{1} < m + 1 and L w_{1} ≠ m. Obviously, spi w′ = m + 1 and grn w′ = k by (6.12).

Let us now prove that w′ is André I. Note that the troughs remain the same in both w and w′. Let x be a trough within w_{2} and (v_{1}, v_{2}, x, v_{4}, v_{5}) (respectively (v′_{1}, v′_{2}, x, v′_{4}, v′_{5})) be the x-factorization of w (respectively of w′). When going from w to w′, the type of x is not modified when at least one of the following conditions holds: max v_{2} ≠ m, max v_{4} ≠ m + 1. If both were violated for a given x, it would be the case for x = min w_{2}, and all the letters of w_{2} would be less than m. But max v_{4} = m+1 implies max v_{4} > F w_{3} > min w_{2}, and F w_{3} is a trough of w. If (v′′_{1}, v′′_{2}, F w_{3}, v′′_{4}, v′′_{5}) is the F w_{3}-factorization of w, the word F w_{3} v′′_{4} is necessarily a factor of v_{4}, as all its letters are greater than min w_{2}. Hence, max v_{4} > m + 1, a contradiction. Thus,

w′ is an unhooked permutation from And_{n}^{I} such that spi w′ = m + 1, grn w′ =k with (m+1) to the left of m. In short, w′ ∈ NH_{n}^{(1)}(m + 1, k).

As the transposition w_{1} (m + 1) w_{2} m w_{3} ↦ w_{1} m w_{2} (m + 1) w_{3}, when applied to André I permutations with (m + 1) to the left of m, always maps an André I onto an André I permutations,

the direct transposition β defined in (6.13) is a bijection between B_{n}^{(1)}(m, k) and NH_{n}^{(1)}(m + 1, k).

Next, let w belong to B_{n}^{(2)}(m, k), and consider the permutation w′ = β(w) defined in (6.14). The left factor ρ^{−1}αρ(v_{1}) of β(w) is André I and ends with (m+1). Therefore, β(w) is of the form w′_{1} m w′_{2} (m+1) w_{3}. Again, with the hypothesis (6.12), the letter x_{n−1}, equal to k in the permutation w = x_{1}x_{2} ⋯ k n, remains untouched when going from w to w′. Thus, grn w′ = grn w = k. Next, we get spi ρ(v_{1}) = n′ − 1 and spi αρ(v_{1}) = n′; hence, spi ρ^{−1}αρ(v_{1}) = m + 1. As w_{3} starts with a letter less than all the letters in v_{1}, we have spi w′ = spi ρ^{−1}αρ(v_{1}) w_{3} = m + 1. Moreover, w_{3} is André I by Proposition 2.1 (5), so that β(w) is André I by Proposition 2.1 (7). This shows that

the mapping β defined in (6.14) is a bijection between B_{n}^{(2)}(m, k) and the set NH_{n}^{(2)}(m + 1, k), defined as the set of all unhooked permutations from And_{n}^{I} such that spi w′ = m + 1, grn w′ = k with m to the left of (m + 1).

This proves the following theorem.

Theorem 6.6. Under condition (6.12), the mapping β : w ↦ w′ defined in (6.13) and (6.14) is a bijection between B_{n}(m, k) = B_{n}^{(1)}(m, k) ⊎ B_{n}^{(2)}(m, k) and NH_{n}(m + 1, k) = NH_{n}^{(1)}(m + 1, k) ⊎ NH_{n}^{(2)}(m + 1, k).

[figure: 1; 2; 3; 4; 5; k; m; 1; 2; 3; 4; 5; 324516; 314526; 423516; 342516; 413526; 341526; 435126; 241536; 412536; 415236; 425136; 234516; 243516; 345126; 351426; 513426; 451326; 245136; 514236; 512436; 251436; 451236; 214536; 213546; 215346; 315246; 312546; 231546; 325146; 213456; 214356; 314256; 231456; 324156; 312456; 412356; 234156; 241356; 413256; 341256]

Table 6.4: the bijection β : B_{6}(m, k) → NH_{6}(m + 1, k)

Example. In Table 6.4, the image β(w) of each André I permutation w from B_{6}(m, k), with (m, k) satisfying inequalities (6.12) for n = 6, is indicated by a downarrow. The hooked permutations are reproduced in boldface. Note that they are not bottoms of any downarrows, as β is a bijection between B_{n}(m, k) and NH_{n}(m + 1, k).

With the construction of the bijection β : B_{n}(m, k) → NH_{n}(m + 1, k), the program displayed in (1.14) is completed, as

Δ_{(1)} b_{n}(m, k) = #B_{n}(m + 1, k) − #B_{n}(m, k)
= #B_{n}(m + 1, k) − #NH_{n}(m + 1, k)
= #H_{n}(m + 1, k)
= #A_{n−1}(m, k) (respectively = #A_{n−1}(m, k − 1))

if 1 ≤ k < m ≤ n − 2 (respectively if 3 ≤ m + 2 ≤ k ≤ n − 1).

7. The making of Seidel triangle sequences

7.1. The Seidel tangent-secant matrix. In the sequel, three 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)\frac{x^{m}}{m!} \frac{y^{k}}{k!} ;

A_{m,•}(y) := ∑_{k≥0} a(m, k)\frac{y^{k}}{k!} ; A_{•,k}(x) := ∑_{m≥0} a(m, k)\frac{x^{m}}{m!} ;

for A itself, its m-th row, its k-th column. Let \overline{H} = (\overline{h}_{i,j}) (i, j ≥ 0) be the infinite matrix whose entries are the Entringer numbers E_{n}(m) displayed along the skew-diagonals with the following sign:

(7.1) \overline{h}_{i,j} = \{ \begin{matrix}(−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; \end{matrix}

or still (7.2) E_{2n+1}(j + 1) = (−1)^{n} \overline{h}_{2n−j,j} (0 ≤ j ≤ 2n); (7.3) E_{2n}(i + 1) = (−1)^{n} \overline{h}_{i,2n−1−i} (0 ≤ i ≤ 2n − 1);

or still in displayed form:

\overline{H} =( E_{1}(1) −E_{2}(1)  0  E_{4}(1)  0  −E_{6}(1) 0 ⋯; 0  −E_{3}(2) E_{4}(2) E_{5}(4) −E_{6}(2) −E_{7}(6) ; −E_{3}(1) E_{4}(3) E_{5}(3) −E_{6}(3) −E_{7}(5) ; 0  E_{5}(2) −E_{6}(4) −E_{7}(4) ; E_{5}(1) −E_{6}(5) −E_{7}(3) ; 0  −E_{7}(2) ; −E_{7}(1) ; ⋮ )

= ( 1 −1 0  2  0 −16 0 ⋯; 0 −1 2  2 −16 −16 ; −1 1  4 −14 −32 ; 0  5 −10 −46 ; 5 −5 −56 ; 0 −61 ; −61 ; ⋮ ) .

As noted by Dumont [Du82], the definition of such a matrix \overline{H} goes back to Seidel himself [Se1877]. Entringer [En66] rediscovered the absolute values of the entries, when he classified the alternating permutations according to their first letters. The entries of the top row are the coefficients of the Taylor expansion of 1 − tanh y = 2/(1 + e^{2y}):

\overline{H}_{0,•}(y) = 1 − tanh y = 1 + ∑_{n≥1} \frac{y^{2n−1}}{(2n − 1)!}(−1)^{n}E_{2n−1}

= 1 − \frac{y}{1!}1+ \frac{y^{3}}{3!} 2− \frac{y^{5}}{5!} 16+ \frac{y^{7}}{7!} 272− \frac{y^{9}}{9!} 7936+· · · .

The entries of the leftmost column are the coefficients of the Taylor expansion of 1/ cosh x = 2 e^{x}/(1 + e^{2x}), so that

\overline{H}_{•,0}(x) = \frac{1}{cosh x} = ∑_{n≥0} \frac{x^{2n}}{(2n)!}(−1)^{n} E_{2n}

= 1 − \frac{x^{2}}{2!} + \frac{x^{4}}{4!} 5 − \frac{x^{6}}{6!} 61 + \frac{x^{8}}{8!} 1385 − · · · .

By means of recurrence (1.1) satisfied by the Entringer numbers and (7.1), we can verify that the entries \overline{h}_{i,j} obey the following rule: \overline{h}_{i,j} = \overline{h}_{i−1,j} + \overline{h}_{i−1,j+1} for j ≥ 0, i ≥ 1, so that the entries \overline{h}_{i,j} can be obtained by applying such a rule inductively, the entries of the top row being given. Such a matrix is called a Seidel matrix by Dumont [Du82], and its exponential generating function is directly obtained from the exponential generating function for its top row by the formula \overline{H}(x, y) = \overline{H}_{0,•}(x+y) e^{x} (see, e.g., [DV80]). Accordingly,

(7.4)  \overline{H}(x, y) = \frac{2 e^{x}}{1 + e^{2x+2y}} .

Two further matrices are derived from \overline{H}. The first one, \overline{H}_{1}, is obtained by replacing all the entries \overline{h}_{i,j} such that i + j is odd by zero, so that

\overline{H}_{1} = ( 1  ·  0  ·  0  · 0 ⋯; ·  −1  ·  2  · −16 ; −1  ·  4  · −32 ; ·  5  · −46 ; 5  · −56 ; · −61 ; −61 ; ⋮ ) .

As \overline{H}(x, y) = \frac{2e^{x}}{1 + e^{2x+2y}}, we get

(7.5) \overline{H}_{1}(x, y) = \frac{\overline{H}(x, y) + \overline{H}(−x, −y)}{2} = e^{x} \frac{1 + e^{2y}}{1 + e^{2x+2y}} = \frac{cosh y}{cosh(x + y)}.

The second one, \overline{H}_{2}, is derived from \overline{H} by replacing the entries \overline{h}_{i,j} such that i + j is even by 0, so that

\overline{H}_{2} = ( · −1 ·  2  · −16 · 272 ⋯; 0 ·  2  · −16 · 272 ; · 1  · −14 · 256 ; 0 · −10 · 224 ; · −5 · 178 ; 0 · 122 ; · 61 ; 0 ; ⋮ ) .

Therefore,

(7.6) \overline{H}_{2}(x, y) = \frac{\overline{H}(x, y) − \overline{H}(−x, −y)}{2} = e^{x} \frac{1 − e^{2y}}{1 + e^{2x+2y}} = \frac{− sinh y}{cosh(x + y)}.

In the sequel, further matrices will be derived from \overline{H}_{1} and \overline{H}_{2}, essentially by transposing them and/or removing either their top rows or leftmost columns. The corresponding actions on their respective exponential generating functions \overline{H}_{1}(x, y) and \overline{H}_{2}(x, y) are the exchange of the variables x and y: T H_{i}(x, y) := H_{i}(y, x); then, the partial derivatives with respect to x and y: D_{x}H_{i}(x, y) and D_{y}H_{i}(x, y) (i = 1, 2).

7.2. The generating function for the Entringer numbers. The generating function for the Entringer numbers, already derived in [FH14], can be obtained from relations (7.5) and (7.6). In fact, they are simply equal to \overline{H}_{1}(xI, yI) and I\overline{H}_{2}(xI, yI), where I = \sqrt{−1}. Thus,

(7.7) ∑_{1≤k≤2n+1} E_{2n+1}(k)\frac{x^{2n+1−k}}{(2n + 1 − k)!} \frac{y^{k−1}}{(k − 1)!} = \frac{cos y}{cos(x + y)};

(7.8)  ∑_{1≤k≤2n} E_{2n}(k)\frac{x^{k−1}}{(k − 1)!} \frac{y^{2n−k}}{(2n − k)!} = \frac{sin y}{cos(x + y)}.

7.3. Seidel triangle sequences. For calculating the generating functions for the twin Seidel matrices, we shall take recourse to the techniques developed in our previous paper [FH14] for the so-called Seidel triangle sequences. Only definitions will be stated, as well as the main result.

A sequence of square matrices (C_{n}) (n ≥ 1) is called a Seidel triangle sequence if the following three conditions are fulfilled:

(STS1) each matrix C_{n} is of dimension n;

(STS2) each matrix C_{n} has zero entries along and below its diagonal; let (c_{n}(m, k)) (0 ≤ m < k ≤ n − 1) denote its entries strictly above its diagonal, so that

C_{1} = ( ·) ; C_{2} = ( \begin{matrix}· & c_{2}(0, 1) \\ · & · \end{matrix} ); C_{3} = ( \begin{matrix}· & c_{3}(0, 1) & c_{3}(0, 2) \\ · & · & c_{3}(1, 2) \\ · & · & · \end{matrix} ); …;

C_{n} = ( \begin{matrix}· & c_{n}(0, 1) & c_{n}(0, 2) & ⋯ & · & c_{n}(0, n − 2) & c_{n}(0, n − 1) \\ · & · & c_{n}(1, 2) & ⋯ & · & c_{n}(1, n − 2) & c_{n}(1, n − 1) \\ ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ & ⋮ \\ · & · & · & ⋯ & · & · & c_{n}(n − 2, n − 1) \\ · & · & · & ⋯ & · & · & · \end{matrix} );

the dots “·” along and below the diagonal referring to zero entries. (STS3) for each n ≥ 3, the following relation holds:

c_{n}(m, k) − c_{n}(m, k + 1) = c_{n−1}(m, k) (m < k).

Record the last columns of the triangles C_{2}, C_{3}, C_{4}, C_{5}, …, read from top to bottom, namely, c_{2}(0, 1); c_{3}(0, 2), c_{3}(1, 2); c_{4}(0, 3), c_{4}(1, 3), c_{4}(2, 3); c_{5}(0, 4), c_{5}(1, 4), c_{5}(2, 4), c_{5}(3, 4); …, as skew-diagonals of an infinite matrix H = (h_{i,j})_{i,j≥0}, as shown next:

(7.9) H := ( \begin{matrix}& 0 & 1 & 2 & 3 & 4 & ⋯ \\ 0 & c_{2}(0, 1) & c_{3}(1, 2) & c_{4}(2, 3) & c_{5}(3, 4) & c_{6}(4, 5) & ⋯ \\ 1 & c_{3}(0, 2) & c_{4}(1, 3) & c_{5}(2, 4) & c_{6}(3, 5) \\ 2 & c_{4}(0, 3) & c_{5}(1, 4) & c_{6}(2, 5) \\ 3 & c_{5}(0, 4) & c_{6}(1, 5) \\ 4 & c_{6}(0, 5) \\ ⋮ & ⋮ \end{matrix} ),

Equivalently, the entries of H are defined by

(7.10)  h_{i,j} = c_{i+j+2}(j, i + j + 1).

The next theorem has been proved in [FH14] and will be of great use in the next sections.

Theorem 7.1. The three-variable generating function for the Seidel triangle sequence (C_{n} = (c_{n}(m, k)))_{n≥1} is equal to

(7.11) ∑_{1≤m+1≤k≤n−1} c_{n}(m, k)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!} = e^{x}H(x + y, z),

where H is the infinite matrix defined in (7.10).

With I := \sqrt{−1}, we get

(7.12) ∑_{1≤m+1≤k≤n−1} I^{n−2}c_{n}(m, k)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= e^{Ix}H(Ix + Iy, Iz).

8. Trivariate generating functions

Each of the sequences Twin^{(1)} := (A_{2}, B_{3}, A_{4}, B_{5}, A_{6}, …) and Twin^{(2)} := (B_{2}, A_{3}, B_{4}, A_{5}, B_{6}, …) (see Diagram 1.3) gives rise to two Seidel triangle sequences, by considering the upper and lower triangles of the matrices.

8.1. The upper triangles of Twin^{(1)}. The Seidel triangle sequence to be constructed is the following: first, C_{1} := (·), then for n ≥ 2 each C_{n} will be derived from the upper triangle of A_{n+1} (respectively B_{n+1}) by (i) dropping the rightmost column; (ii) transposing the remaining triangle with respect to its skew-diagonal; (iii) changing the signs of its entries according the following rule. More precisely,

C_{n} := (−1)^{(n+1)/2} (\begin{matrix}· & a_{n+1}(n − 1, n) & ⋯ & a_{n+1}(2, n) & a_{n+1}(1, n) \\ & & ... & ⋮ & ⋮ \\ & & · & a_{n+1}(2, 3) & a_{n+1}(1, 3) \\ & & & · & a_{n+1}(1, 2) \\ & & & & · \end{matrix}) if n is odd;

C_{n} := (−1)^{n/2} (\begin{matrix}· & b_{n+1}(n − 1, n) & ⋯ & b_{n+1}(2, n) & b_{n+1}(1, n) \\ & & ... & ⋮ & ⋮ \\ & & · & b_{n+1}(2, 3) & b_{n+1}(1, 3) \\ & & & · & b_{n+1}(1, 2) \\ & & & & · \end{matrix}) if n is even;

By referring to Diagram 1.3, we get C_{1} = · ; C_{2} = \begin{aligned}· & 0 \\ & · \end{aligned}; C_{3} = \begin{aligned}· & 1 & 1 \\ & · & 1 \\ & & · \end{aligned};

C_{4} = \begin{aligned}· & 2 & 1 & 0 \\ & · & 1 & 0 \\ & & · & 0 \\ & & & · \end{aligned} ; C_{5} = \begin{aligned}· & −2 & −4 & −5 & −5 \\ & · & −4 & −5 & −5 \\ & & · & −4 & −4 \\ & & & · & −2 \\ & & & & · \end{aligned} ; C_{6} = \begin{aligned}· & −16 & −14 & −10 & −5 & 0 \\ & · & −14 & −10 & −5 & 0 \\ & & · & −8 & −4 & 0 \\ & & & · & −2 & 0 \\ & & & & · & 0 \\ & & & & & · \end{aligned};

C_{7} = \begin{aligned}· & 16 & 32 & 46 & 56 & 61 & 61 \\ & · & 32 & 46 & 56 & 61 & 61 \\ & & · & 44 & 52 & 56 & 56 \\ & & & · & 44 & 46 & 46 \\ & & & & · & 32 & 32 \\ & & & & & · & 16 \\ & & & & & & · \end{aligned} ; C_{8} = \begin{aligned}· & 272 & 256 & 224 & 178 & 122 & 61 & 0 \\ & · & 256 & 224 & 178 & 122 & 61 & 0 \\ & & · & 208 & 164 & 112 & 56 & 0 \\ & & & · & 136 & 92 & 46 & 0 \\ & & & & · & 64 & 32 & 0 \\ & & & & & · & 16 & 0 \\ & & & & & & · & 0 \\ & & & & & & & · \end{aligned} .

Therefore,

(8.1)  c_{n}(m, k) = \{ \begin{matrix}(−1)^{(n+1)/2}a_{n+1}(n − k, n − m), & if n is odd; \\ (−1)^{n/2}b_{n+1}(n − k, n − m), & if n is even. \end{matrix}

Proposition 8.1. The sequence (C_{n}) (n ≥ 1) just defined is a Seidel triangle sequence.

Proof. We only have to verify that rule (STS3) holds. If n is odd and 0 ≤ m < k ≤ n − 2, then 3 ≤ m′ + 2 := (n − k − 1) + 2 ≤ k′ := n − m ≤ (n + 1) − 1 and

c_{n}(m, k) − c_{n}(m, k + 1) = (−1)^{(n+1)/2}(a_{n+1}(n − k, n − m) − a_{n+1}(n − k − 1, n − m))

= (−1)^{(n+1)/2} Δ_{(1)} a_{n+1}(n − k − 1, n − m)

= (−1)^{(n+1)/2} Δ_{(1)} a_{n+1}(m′, k′)

= (−1)^{(n−1)/2} b_{n}(m′, k′ − 1) [by rule (TS5.2)] = (−1)^{(n−1)/2} b_{n}(n − k − 1, n − m − 1) = (−1)^{(n−1)/2}(−1)^{(n−1)/2} c_{n−1}(m, k) = c_{n−1}(m, k).

The case when n is even can be proved in a similar way.

The next step is to determine the matrix H, as defined in (7.9), whose skew-diagonals are equal to the rightmost columns of the matrices C_{n}. For n ≥ 2 the skew-diagonal (c_{n}(0, n − 1), c_{n}(1, n − 1), …, c_{n}(n − 2, n − 1)) of H, being the rightmost column of C_{n}, is equal to

\{ \begin{matrix}(−1)^{(n+1)/2}(a_{n+1}(1, n), a_{n+1}(1, n − 1), …, a_{n+1}(1, 2)), & if n is odd, \\ (−1)^{n/2}(b_{n+1}(1, n), b_{n+1}(1, n − 1), …, b_{n+1}(1, 2)), & if n is even; \end{matrix}

which is also equal to

\{ \begin{matrix}(−1)^{(n+1)/2}(b_{n}(•, n − 1), b_{n}(•, n − 2), …, b_{n}(•, 1)), & if n is odd; \\ (0, 0, …, 0 ), & if n is even; \end{matrix}

by Rules (TS5.1) and (TS2); finally, this is equal to

\{ \begin{matrix}(−1)^{(n+1)/2}(E_{n}(1), E_{n}(2), …, E_{n}(n − 1)), & if n is odd; \\ (0, 0, …, 0 ), & if n is even; \end{matrix}

by (1.11).

Thus,

H = ( 0  E_{3}(2)  0  −E_{5}(4) 0 E_{7}(6) 0 ⋯; E_{3}(1)  0  −E_{5}(3)  0  E_{7}(5) 0 ; 0  −E_{5}(2)  0  E_{7}(4)  0 ; −E_{5}(1)  0  E_{7}(3)  0 ; 0  E_{7}(2)  0 ; E_{7}(1)  0 ; 0 ; ⋮ )

(8.2)

= ( 0 1 0 −2 0 16 0 ⋯; 1 0 −4 0 32 0 ; 0 −5 0 46 0 ; −5 0 56 0 ; 0 61 0 ; 61 0 ; 0 ; ⋮ ) .

This matrix is to be compared with the matrix \overline{H}_{1} (see §7.1). For getting H, it suffices to delete the top row of \overline{H}_{1} and change the signs of all the entries. As \overline{H}_{1}(x, y) = cosh y/ cosh(x + y) by (7.5), we have

(8.3)  H(x, y) = −D_{x}\overline{H}_{1}(x, y) = \frac{cosh y sinh(x + y)}{cosh^{2}(x + y)}.

Hence, the right-hand side of (7.11) becomes

e^{x}H(x + y, z) = e^{x} \frac{cosh z sinh(x + y + z)}{cosh^{2}(x + y + z)};

and the right-hand side of (7.12) is equal to

e^{Ix}H(Ix + Iy, Iz) = (cos x + I sin x)\frac{I cos z sin(x + y + z)}{cos^{2}(x + y + z)}.

It remains to interpret the left-hand side of identity (7.12) by using (8.1). If n = 2l + 1, then I^{n−2} = (−1)^{l+1}I and (−1)^{(n+1)/2} = (−1)^{l+1}.

Thus, I^{n−2}c_{n}(m, k) = I a_{n+1}(n−k, n−m). The imaginary part of identity (7.12) then reads

∑_{{1≤m+1≤k≤n−1 \atop n odd}} a_{n+1}(n − k, n − m)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= \frac{cos x cos z sin(x + y + z)}{cos^{2}(x + y + z)}.

With the change of variables n ← 2n − 1, n − k ← m, n − m ← k, we get (1.15) from Theorem 1.3. Note that the above generating function involves all the matrices A_{4}, A_{6}, … of Twin^{(1)}, but not the very first term A_{2} = ({1 0 \atop 0 0}).

If n = 2l, then I^{n−2} = (−1)^{l−1} and (−1)^{n/2} = (−1)^{l}, so that I^{n−2}c_{n}(m, k) = −b_{n+1}(n − k, n − m). As for the real part, we have

∑_{{1≤m+1≤k≤n−1 \atop n even}} b_{n+1}(n − k, n − m)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= \frac{sin x cos z sin(x + y + z)}{cos^{2}(x + y + z)}.

With the change of variables n ← 2n, n − k ← m, n − m ← k, we get (1.21) from Theorem 1.6.

8.2. The upper triangles of Twin^{(2)}. The sequence of triangles to be considered is the following: C_{1} = · and for n ≥ 2

C_{n} := (−1)^{(n−1)/2} (\begin{matrix}· & b_{n+1}(n − 1, n) & ⋯ & b_{n+1}(2, n) & b_{n+1}(1, n) \\ & & ... & ⋮ & ⋮ \\ & & · & b_{n+1}(2, 3) & b_{n+1}(1, 3) \\ & & & · & b_{n+1}(1, 2) \\ & & & & · \end{matrix}) if n is odd;

C_{n} := (−1)^{n/2} (\begin{matrix}· & a_{n+1}(n − 1, n) & ⋯ & a_{n+1}(2, n) & a_{n+1}(1, n) \\ & & ... & ⋮ & ⋮ \\ & & · & a_{n+1}(2, 3) & a_{n+1}(1, 3) \\ & & & · & a_{n+1}(1, 2) \\ & & & & · \end{matrix}) if n is even;

that is, C_{1} = ·, C_{2} = \begin{aligned}· & −1 \\ & · \end{aligned}; C_{3} = \begin{aligned}· & −1 & 0 \\ & · & 0 \\ & & · \end{aligned}; C_{4} = \begin{aligned}· & 1 & 2 & 2 \\ & · & 2 & 2 \\ & & · & 1 \\ & & & · \end{aligned};

C_{5} = \begin{aligned}· & 5 & 4 & 2 & 0 \\ & · & 4 & 2 & 0 \\ & & · & 1 & 0 \\ & & & · & 0 \\ & & & & · \end{aligned}; C_{6} = \begin{aligned}· & −5 & −10 & −14 & −16 & −16 \\ & · & −10 & −14 & −16 & −16 \\ & & · & −13 & −14 & −14 \\ & & & · & −10 & −10 \\ & & & & · & −5 \\ & & & & & · \end{aligned};

C_{7} =\begin{aligned}· & −61 & −56 & −46 & −32 & −16 & 0 \\ & · & −56 & −46 & −32 & −16 & 0 \\ & & · & −41 & −28 & −14 & 0 \\ & & & · & −20 & −10 & 0 \\ & & & & · & −5 & 0 \\ & & & & & · & 0 \\ & & & & & & · \end{aligned}; C_{8} = \begin{aligned}· & 61 & 122 & 178 & 224 & 256 & 272 & 272 \\ & · & 122 & 178 & 224 & 256 & 272 & 272 \\ & & · & 173 & 214 & 242 & 256 & 256 \\ & & & · & 194 & 214 & 224 & 224 \\ & & & & · & 173 & 178 & 178 \\ & & & & & · & 122 & 122 \\ & & & & & & · & 61 \\ & & & & & & & . \end{aligned}.

Thus,

(8.6)  c_{n}(m, k) = \{ \begin{matrix}(−1)^{(n−1)/2}b_{n+1}(n − k, n − m), & if n is odd; \\ (−1)^{n/2}a_{n+1}(n − k, n − m), & if n is even. \end{matrix}

The sequence of triangles (C_{n}) defined by (8.6) is a Seidel triangle sequence (same argument as in the proof of Proposition 8.1). Following the same pattern as in the preceding subsection, we form the matrix H, whose skew-diagonals carry the entries of the leftmost columns of the C_{n}’s:

H = ( −1 0  1  0 −5 0 61 ⋯; 0  2  0 −10 0 122 ; 2  0 −14 0 178 ; 0 −16 0 224 ; −16 0 256 ; 0 272 ; 272 ; ⋮ ) .

This matrix is to be compared with the matrix \overline{H}_{2} (see Subsection 7.2). We see that H is obtained from \overline{H}_{2} by transposition and deletion of the first row, so that

H(x, y) = D_{x}\overline{H}_{2}(y, x) = D_{x}(\frac{− sinh x}{cosh(x + y)})

= \frac{− cosh x cosh(x + y) + sinh x sinh(x + y)}{cosh^{2}(x + y)}

= \frac{− cosh y}{cosh^{2}(x + y)}.

Therefore,

e^{x}H(x + y, z) = e^{x} \frac{− cosh z}{cosh^{2}(x + y + z)};
e^{Ix}H(Ix + Iy, Iz) = (cos x + I sin x)\frac{− cos z}{cos^{2}(x + y + z)}.

By using (8.6), the left-hand side of identity (7.12) can be computed as follows. If n = 2l + 1, then I^{n−2} = (−1)^{l+1}I and (−1)^{(n−1)/2} = (−1)^{l}. Thus, I^{n−2}c_{n}(m, k) = −I b_{n+1}(n − k, n − m). The imaginary part of identity (7.12) reads

∑_{{1≤m+1≤k≤n−1 \atop n odd}} b_{n+1}(n − k, n − m)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= \frac{sin x cos z}{cos^{2}(x + y + z)}.

With the change of variables n ← 2n − 1, n − k ← m, n − m ← k, we get (1.19) from Theorem 1.5.

If n = 2l, then I^{n−2} = (−1)^{l−1} and (−1)^{n/2} = (−1)^{l}, so that I^{n−2}c_{n}(m, k) = −a_{n+1}(n − k, n − m). As for the real part, we have

∑_{{1≤m+1≤k≤n−1 \atop n even}} a_{n+1}(n − k; n − m)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= \frac{cos x cos z}{cos^{2}(x + y + z)}.

With the change of variables n ← 2n, n − k ← m, n − m ← k, we get (1.17) from Theorem 1.4.

8.3. The bottom rows of the matrices B_{n}’s. By Rule (TS4.1) and (2.6), these bottom rows, after discarding the rightmost entry which is always zero, read b_{2}(2, 1) = 1; (b_{3}(3, 1), b_{3}(3, 2)) = (0, 1), (b_{4}(4, 1), b_{4}(4, 2), b_{4}(4, 3)) = (0, 1, 1), (b_{5}(5, 1), b_{5}(5, 2), b_{5}(5, 3), b_{5}(5, 4)) = (0, 1, 2, 2), …, which are equal to the sequences of the Entringer numbers: E_{1}(1), (E_{2}(2), E_{2}(1)), (E_{3}(3), E_{3}(2), E_{3}(1)), (E_{4}(4), E_{4}(3), E_{4}(2), E_{4}(1)), … By (7.7) and (7.8), we recover the two identities (1.23) and (1.24) written at the end of Section 1.

8.4. The lower triangles of Twin^{(1)}. As for the upper triangles, a geometric transformation is to be made to configurate these lower triangles into Seidel triangles. The bottom rows of the A_{n}’s and B_{n}’s being discarded, we form the following sequence of triangles:

ANDRÉ PERMUTATION CALCULUS 45

C_{1} = ·; C_{2} = \begin{aligned}· & 1 \\ & · \end{aligned}; C_{3} =\begin{aligned}· & 1 & 0 \\ & · & 1 \\ & & · \end{aligned}; C_{4} =\begin{aligned}· & 0 & −1 & −1 \\ & · & −1 & −2 \\ & & · & −2 \\ & & & · \end{aligned}; C_{5} =\begin{aligned}· & −2 & −2 & −1 & 0 \\ & · & −4 & −3 & −1 \\ & & · & −4 & −2 \\ & & & · & −2 \\ & & & & · \end{aligned};

C_{6} = \begin{aligned}· & 0 & 2 & 4 & 5 & 5 \\ & · & 2 & 6 & 9 & 10 \\ & & · & 8 & 12 & 14 \\ & & & · & 14 & 16 \\ & & & & · & 16 \\ & & & & & · \end{aligned}; C_{7} = \begin{aligned}· & 16 & 16 & 14 & 10 & 5 & 0 \\ & · & 32 & 30 & 24 & 15 & 5 \\ & & · & 44 & 36 & 24 & 10 \\ & & & · & 44 & 30 & 14 \\ & & & & · & 32 & 16 \\ & & & & & · & 16 \\ & & & & & & · \end{aligned};

Thus, for 0 ≤ m < k ≤ n − 1, we have

(8.9)  c_{n}(m, k) = \{ \begin{matrix}(−1)^{(n+1)/2}a_{n+1}(k + 1, m + 1), & if n is odd; \\ (−1)^{(n+2)/2}b_{n+1}(k + 1, m + 1), & if n is even. \end{matrix}

The sequence of triangles (C_{n}) defined by (8.9) is a Seidel triangle sequence. The corresponding matrix H reads

H = ( 1 1 −2 −2 16 16 ⋯; 0 −2 −2 16 16 ; −1 −1 14 14 ; 0 10 10 ; 5 5 ; 0 ; ⋮ )

= ( 1 . −2 . 16 ⋯; . −2 . 16 . ; −1 . 14 . ; . 10 . ; 5 . ; ⋮ )+( . 1 . −2 . 16 ⋯; 0 . −2 . 16 ; . −1 . 14 ; 0 . 10 ; . 5 ; 0 ; ⋮ )

= −D_{y}\overline{H}_{2} − \overline{H}_{2}. Thus,

H(x, y) = D_{y} \frac{sinh y}{cosh(x + y)} + \frac{sinh y}{cosh(x + y)}

(8.10) = \frac{cosh x}{cosh^{2}(x + y)} + \frac{sinh y}{cosh(x + y)};

e^{x}H(x + y, z) = e^{x}(\frac{cosh(x + y)}{cosh^{2}(x + y + z)} + \frac{sinh z}{cosh(x + y + z)});
e^{Ix}H(Ix + Iy, Iz) = (cos x + I sin x)(\frac{cos(x + y)}{cos^{2}(x + y + z)} + \frac{I sin z}{cos(x + y + z)}).

If n = 2l + 1, then I^{n−2} = (−1)^{l+1}I and (−1)^{(n+1)/2} = (−1)^{l+1}. Thus, I^{n−2}c_{n}(m, k) = I a_{n+1}(k +1, m+1). The imaginary part of identity (7.12) becomes

∑_{{1≤m+1≤k≤n−1 \atop n odd}} a_{n+1}(k + 1, m + 1)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= \frac{cos x sin z}{cos(x + y + z)} + \frac{sin x cos(x + y)}{cos^{2}(x + y + z)}.

With the change of variables n ← 2n − 1, k + 1 ← m, m + 1 ← k, we get (1.16) from Theorem 1.3.

If n = 2l, then I^{n−2} = (−1)^{l−1} and (−1)^{(n+2)/2} = (−1)^{l+1}, so that I^{n−2}c_{n}(m, k) = b_{n+1}(k + 1, m + 1). As for the real part, we have

∑_{{1≤m+1≤k≤n−1 \atop n even}} b_{n+1}(k + 1, m + 1)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= −\frac{sin x sin z}{cos(x + y + z)} + \frac{cos x cos(x + y)}{cos^{2}(x + y + z)}.

With the change of variables n ← 2n, k + 1 ← m, m + 1 ← k, we get (1.22) from Theorem 1.6.

8.5. The lower triangles of Twin^{(2)}. Again, the bottom rows of the A_{n}’s and B_{n}’s having been discarded, the Seidel triangle sequence to be considered is

C_{1} = ·; C_{2} = \begin{aligned}· & 1 \\ & · \end{aligned}; C_{3} = \begin{aligned}· & 0 & −1 \\ & · & −1 \\ & & · \end{aligned}; C_{4} = \begin{aligned}· & −1 & −1 & 0 \\ & · & −2 & −1 \\ & & · & −1 \\ & & & · \end{aligned} C_{5} = \begin{aligned}· & 0 & 1 & 2 & 2 \\ & · & 1 & 3 & 4 \\ & & · & 4 & 5 \\ & & & · & 5 \\ & & & & · \end{aligned};

C_{6} = \begin{aligned}· & 5 & 5 & 4 & 2 & 0 \\ & · & 10 & 9 & 6 & 2 \\ & & · & 13 & 9 & 4 \\ & & & · & 10 & 5 \\ & & & & · & 5 \\ & & & & & · \end{aligned}; C_{7} = \begin{aligned}· & 0 & −5 & −10 & −14 & −16 & −16 \\ & · & −5 & −15 & −24 & −30 & −32 \\ & & · & −20 & −33 & −42 & −46 \\ & & & · & −41 & −51 & −56 \\ & & & & · & −56 & −61 \\ & & & & & · & −61 \\ & & & & & & · \end{aligned};

the general formula being

(8.13) c_{n}(m, k) = \{ \begin{matrix}(−1)^{(n−1)/2}b_{n+1}(k + 1, m + 1), & if n is odd; \\ (−1)^{(n−2)/2}a_{n+1}(k + 1, m + 1), & if n is even. \end{matrix}

Next, form the matrix H, whose skew-diagonals carry the entries of the rightmost columns of the c_{n}’s, and write it as the sum of the two matrices

H = ( 1 −1 −1 5  5 −61 −61 ⋯; −1 −1 5  5 −61 −61 ; 0  4  4 −56 −56 ; 2  2 −46 −46 ; 0 −32 −32 ; −16 −16 ; 0 ; ⋮ ) := K_{1} + K_{2}

=(1 · −1 · 5 · −61 ⋯; · −1 · 5 · −61 ; 0 · 4 · −56 ; · 2 · −46 ; 0 · −32 ; · −16 ; 0 ; ⋮)+( · −1 · 5 · −61 ⋯; −1 · 5 · −61 · ; · 4 · −56 · ; 2 · −46 · ; · −32 · ; −16 · ; ⋮).

These matrices are to be compared with the matrix \overline{H}_{1} (see Section 7). Clearly, K_{2} can be obtained from \overline{H}_{1} by deleting the top row and then transposing the matrix, so that K_{2}(x, y) = T D_{x}\overline{H}_{1}(x, y). Also, K_{1} = T \overline{H}_{1}, and then K_{1}(x, y) = \overline{H}_{1}(y, x). As \overline{H}_{1}(x, y) = cosh y/ cosh(x + y), we get

H(x, y) = T D_{x}\overline{H}_{1}(x, y) + \overline{H}_{1}(y, x)

= −\frac{cosh x sinh(x + y)}{cosh^{2}(x + y)} + \frac{cosh x}{cosh(x + y)};

e^{x}H(x + y, z) = e^{x}(−\frac{cosh(x + y) sinh(x + y + z)}{cosh^{2}(x + y + z)} + \frac{cosh(x + y)}{cosh(x + y + z)});
e^{Ix}H(Ix + Iy, Iz)=(cos x + I sin x)

× (−\frac{I cos(x + y) sin(x + y + z)}{cos^{2}(x + y + z)} + \frac{cos(x + y)}{cos(x + y + z)}).

If n = 2l + 1, then I^{n−2} = (−1)^{l+1}I and (−1)^{(n−1)/2} = (−1)^{l}. Thus, I^{n−2}c_{n}(m, k) = −I b_{n+1}(k + 1, m + 1). The imaginary part of identity (7.12) becomes

∑_{{1≤m+1≤k≤n−1 \atop n odd}} b_{n+1}(k + 1, m + 1)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= −\frac{sin x cos(x + y)}{cos(x + y + z)} + \frac{cos x cos(x + y) sin(x + y + z)}{cos^{2}(x + y + z)}

= \frac{cos(x + y) sin(y + z)}{cos^{2}(x + y + z)}.

With the change of variables n ← 2n − 1, m + 1 ← k, k + 1 ← m, we get (1.20) from Theorem 1.5.

If n = 2l, then I^{n−2} = (−1)^{l−1} and (−1)^{(n−2)/2} = (−1)^{l−1}, so that I^{n−2}c_{n}(m, k) = a_{n+1}(k + 1, m + 1). As for the real part, we have

∑_{{1≤m+1≤k≤n−1 \atop n even}} a_{n+1}(k + 1, m + 1)\frac{x^{n−k−1}}{(n − k − 1)!} \frac{y^{k−m−1}}{(k − m − 1)!} \frac{z^{m}}{m!}

= \frac{cos x cos(x + y)}{cos(x + y + z)} + \frac{sin x cos(x + y) sin(x + y + z)}{cos^{2}(x + y + z)}

= \frac{cos(x + y) cos(y + z)}{cos^{2}(x + y + z)}.

With the change of variables n ← 2n − 1, k + 1 ← m, m + 1 ← k, we get (1.18) from Theorem 1.4.

9. The formal Laplace transform

The purpose of this section is to show that, when the Entringer numbers E_{n}(k) are defined by relations (1.1), without any reference to their combinatorial interpretations, they can be proved to be a refinement of the tangent/secant numbers: ∑_{k} E_{n}(k) = E_{n} (n ≥ 1). In the same manner, when the twin Seidel matrix sequence (A_{n}), (B_{n}) is analytically defined, as it was stated in Subsection 1.5, also without reference to any combinatorial interpretation, their entries (a_{n}(m, k)), (b_{n}(m, k)) make up a refinement of the Entringer numbers, by row and by column, and

∑_{m,k} a_{n}(m, k) = ∑_{m,k} b_{n}(m, k) = E_{n}.

The proofs of these results make use of the closed expressions found for the generating functions in the preceding section, and of a well-adapted formal Laplace transform technique.

Theorem 9.1. (1) Let (E_{n}(k)) be the sequence of the Entringer numbers, defined by

E_{1}(1) := 1; E_{n}(n) := 0 for all n ≥ 2;
ΔE_{n}(m) + E_{n−1}(n − m) = 0 (n ≥ 2; m = n − 1, …, 2, 1);

Then,

(9.1) ∑_{1≤k≤2n−1} E_{2n−1}(k) = E_{2n−1}; ∑_{1≤k≤2n} E_{2n}(k) = E_{2n}; (n ≥ 1).

(2) Let (a_{n}(m, k)), (b_{n}(m, k)) be the entries of the twin

Seidel matrix sequence (A_{n}), (B_{n}), as they are defined in Subsection 1.5. Then,

(9.2) a_{n}(m, •) = E_{n}(m), b_{n}(m, •) = E_{n}(n + 1 − m), (1 ≤ m ≤ n);
(9.3) a_{n}(•, k) = b_{n}(•, k) = E_{n}(n − k) (1 ≤ k ≤ n).

The proof of (9.1) is fully given. Next, we reproduce the proof of a_{2n}(m, •) = E_{2n}(m), based on Theorem 1.3. The other identities in (9.2) and (9.3) can also be derived following the same method by using Theorems 1.4, 1.5, 1.6. Their proofs are omitted.

The formal Laplace transform, already used in our previous paper [FH14], maps a function f(x) to a function L(f(x), x, s) defined by

L(f(x), x, s) : = ∫_{0}^{∞} f(x)e^{−xs} dx.

In particular, L(•, x, s) maps x^{k}/k! to 1/s^{k+1}:

L(\frac{x^{k}}{k!} , x, s) = \frac{1}{s^{k+1}} .

For proving (9.1), start with identity (7.7) involving the generating function for the numbers E_{2n+1}(k) and apply the Laplace transform twice with respect to (x, s), (y, t), respectively. We get

∑_{1≤k≤2n+1} \frac{1}{s^{2n−k+2}} \frac{1}{t^{k}} E_{2n+1}(k) = ∫_{0}^{∞}∫_{0}^{∞} \frac{cos y}{cos(x + y)}e^{−xs−yt}dx dy,

which becomes, with t ← s and r = x + y,

∑_{1≤k≤2n+1} \frac{1}{s^{2n+2}} E_{2n+1}(k) = ∫_{0}^{∞}∫_{0}^{∞} \frac{cos y}{cos(x + y)}e^{−xs−ys}dx dy

= ∫_{0}^{∞}∫_{0}^{r} \frac{cos y}{cos r} e^{−rs}dy dr

= ∫_{0}^{∞} \frac{sin r}{cos r} e^{−rs}dr

= ∫_{0}^{∞}(tan r)e^{−rs}dr

= ∑_{n≥1} \frac{1}{s^{2n}} E_{2n−1}.

Hence,

∑_{1≤k≤2n−1} E_{2n−1}(k) = E_{2n−1}.

In the same manner, apply the Laplace transform to identity (7.8) twice with respect to (x, s), (y, t), respectively. We get

∑_{1≤k≤2n} \frac{1}{s^{k}} \frac{1}{t^{2n−k+1}} E_{2n}(k) = ∫_{0}^{∞}∫_{0}^{∞} \frac{sin y}{cos(x + y)}e^{−xs−yt}dx dy,

which becomes, with s ← t and r = x + y,

∑_{1≤k≤2n} \frac{1}{t^{2n+1}} E_{2n}(k) = ∫_{0}^{∞}∫_{0}^{∞} \frac{sin y}{cos(x + y)}e^{−xt−yt}dx dy

= ∫_{0}^{∞}∫_{0}^{r} \frac{sin y}{cos r} e^{−rt}dy dr

= ∫_{0}^{∞} \frac{1 − cos r}{cos r} e^{−rt}dr

= ∫_{0}^{∞}(sec r − 1)e^{−rt}dr

= ∑_{n≥1} \frac{1}{t^{2n+1}} E_{2n}.

Hence,

∑_{1≤k≤2n} E_{2n}(k) = E_{2n}.

Next, to prove a_{2n}(m, •) = E_{2n}(m) start with identity (1.15) of Theorem 1.5 and apply the Laplace transform to its left-hand side three times with respect to (x, s), (y, t), (z, u), respectively. We get

∑_{2≤m+1≤k≤2n−1} \frac{1}{s^{m}} \frac{1}{t^{k−m}} \frac{1}{u^{2n−k}} a_{2n}(m, k),

which becomes

(9.4)  ∑_{2≤m+1≤k≤2n−1} \frac{1}{s^{m}} \frac{1}{u^{2n}} a_{2n}(m, k),

when t ← u and s ← su. Apply the Laplace transform to the right-hand side of (1.15) three times with respect to (x, s), (y, t), (z, u), respectively, and let t ← u, s ← su. With r = y + z, we get

∫_{0}^{∞}∫_{0}^{∞}∫_{0}^{∞} \frac{cos x cos z sin(x + y + z)}{cos^{2}(x + y + z)}e^{−xsu−yu−zu}dx dy dz

= ∫_{0}^{∞}∫_{0}^{∞}∫_{0}^{r} \frac{cos x cos z sin(x + r)}{cos^{2}(x + r)}e^{−xsu−ru}dz dr dx

(9.5) = ∫_{0}^{∞}∫_{0}^{∞} \frac{cos x sin r sin(x + r)}{cos^{2}(x + r)}e^{−xsu−ru}dr dx.

With identity (1.16) apply the Laplace transform to its left-hand side three times with respect to (x, u), (y, s), (z, t), respectively. We get

∑_{2≤k+1≤m≤2n−1} \frac{1}{u^{2n−m}} \frac{1}{s^{m−k}} \frac{1}{t^{k}} a_{2n}(m, k),

which becomes

(9.6)  ∑_{2≤k+1≤m≤2n−1} \frac{1}{s^{m}} \frac{1}{u^{2n}} a_{2n}(m, k),

when s ← su and t ← su. Apply the Laplace transform to the right-hand side of (1.16) three times with respect to (x, u), (y, s), (z, t), respectively, and let s ← su, t ← su. With r = y + z we get

∫_{0}^{∞}∫_{0}^{∞}∫_{0}^{∞}(\frac{cos x sin z}{cos(x + y + z)} + \frac{sin x cos(x + y)}{cos^{2}(x + y + z)})e^{−xu−ysu−zsu}dx dy dz

= ∫_{0}^{∞}∫_{0}^{∞}∫_{0}^{r}(\frac{cos x sin z}{cos(x + r)} + \frac{sin x cos(x + r − z)}{cos^{2}(x + r)})e^{−xu−rsu}dz dr dx

= ∫_{0}^{∞}∫_{0}^{∞}(\frac{cos x (1 − cos r)}{cos(x + r)} + \frac{sin x (sin(x + r) − sin x)}{cos^{2}(x + r)})e^{−xu−rsu}dr dx

(9.7) =∫_{0}^{∞}∫_{0}^{∞}(\frac{cos r (1−cos x)}{cos(x + r)} + \frac{sin r (sin(x + r)−sin r)}{cos^{2}(x + r)})e^{−ru−xsu}dr dx.

By (9.4)–(9.7), we have

(9.8) ∑_{1≤k,m≤2n−1; k≠m} \frac{1}{s^{m}} \frac{1}{u^{2n}} a_{2n}(m, k) = ∫_{0}^{∞}∫_{0}^{∞} F (x, r)e^{−xsu−ru}dr dx,

where

F (x, r) = \frac{cos x sin r sin(x + r)}{cos^{2}(x + r)} + \frac{cos r (1 − cos x)}{cos(x + r)} + \frac{sin r (sin(x + r) − sin r)}{cos^{2}(x + r)}

= \frac{cos x}{cos^{2}(x + r)} − 1.

However, from (7.8), we conclude

∑_{1≤m≤2n} E_{2n}(m)\frac{x^{m−1}}{(m − 1)!} \frac{r^{2n−m−1}}{(2n − m − 1)!} = \frac{∂}{∂r} \frac{sin r}{cos(x + r)}

= \frac{cos x}{cos^{2}(x + r)}. (9.9)

Apply the Laplace transform to (9.9) twice with respect to (x, s), (y, u), respectively. We get

∑_{1≤m≤2n} \frac{1}{s^{m}} \frac{1}{u^{2n−m}} E_{2n}(m) = ∫_{0}^{∞}∫_{0}^{∞} \frac{cos x}{cos^{2}(x + r)}e^{−xs−ru}dx dr,

or still

(9.10) ∑_{1≤m≤2n} \frac{1}{s^{m}} \frac{1}{u^{2n}} E_{2n}(m) = ∫_{0}^{∞}∫_{0}^{∞} \frac{cos x}{cos^{2}(x + r)}e^{−xsu−ru}dx dr.

By (9.8) and (9.10), we obtain

∑_{1≤k,m≤2n−1; k≠m} \frac{1}{s^{m}} \frac{1}{u^{2n}} a_{2n}(m, k) = ∑_{1≤m≤2n} \frac{1}{s^{m}} \frac{1}{u^{2n}} E_{2n}(m) − \frac{1}{su^{2}} ,

and then

∑_{1≤k,m≤2n−1} \frac{1}{s^{m}} \frac{1}{u^{2n}} a_{2n}(m, k) = ∑_{1≤m≤2n} \frac{1}{s^{m}} \frac{1}{u^{2n}} E_{2n}(m).

Hence,

∑_{1≤k≤2n−1} a_{2n}(m, k) = E_{2n}(m).

Acknowledgement. The authors would like to thank Volker Strehl very highly for having read the paper so carefully and having singled out its spirit, and also Christian Krattenthaler for his magnificent editorial work.

References

[An1879] Désiré André. Développement de sec x et tan x, C. R. Math. Acad. Sci. Paris, vol. 88, 1879, p. 965–979.

[An1881] Désiré André. Sur les permutations alternées, J. Math. Pures et Appl., vol. 7,

1881, p. 167–184.

[AF80] George Andrews; Dominique Foata. Congruences for the q-secant number, Europ. J. Combin., vol. 1, 1980, p. 283–287.

[AG78] George Andrews; Ira Gessel. Divisibility properties of the q-tangent numbers, Proc. Amer. Math. Soc., vol. 68, 1978, p. 380–384.

[Co74] Louis Comtet. Advanced Combinatorics. D. Reidel/Dordrecht-Holland, Boston, 1974.

[Du82] Dominique Dumont. Matrices d’Euler–Seidel, Séminaire Lotharingien de Combinatoire, B05c (1981), 25 pp. [Formerly: Publ. I.R.M.A. Strasbourg, 1982, 182/S-04, pp. 59–78.]

http://www.mat.univie.ac.at/∼slc/.

[DV80] Dominique Dumont; Gérard Viennot. A combinatorial interpretation of the Seidel generation of Genocchi numbers, Combinatorial mathematics, optimal designs [J. Srivastava, ed., Fort Collins. 1978], pp. 77–87. — Amsterdam, North-Holland, 1980 (Annals of Discrete Math. 6).

[Di74] Filippo Disanto. André permutations, right-to-left and left-to-right minima, Séminaire Lothar. Combin., B70f, 2014, 13 pp.

http://www.mat.univie.ac.at/∼slc/.

[En66] R. C. Entringer. A combinatorial interpretation of the Euler and Bernoulli numbers, Nieuw. Arch. Wisk., vol. 14, 1966, p. 241–246.

[FH01] Dominique Foata; Guo-Niu Han. Arbres minimax et polynômes d’André, Advances in Appl. Math., vol. 27, 2001, p. 367–389.

[FH13] Dominique Foata; Guo-Niu Han. Finite difference calculus for alternating permutations, J. Difference Equations and Appl., vol. 19, 2013, p. 1952–1966.

[FH14] Dominique Foata; Guo-Niu Han. Seidel triangle sequences and Bi-Entringer

numbers, Europ. J. of Combin., vol. 42, 2014, p. 243–260.

[FSch71] Dominique Foata; Marcel-Paul Schützenberger. Nombres d’Euler et permutations alternantes. Manuscript , 71 pages, University of Florida, Gainesville, 1971; available in the “Books” section of the Séminaire Lotharingien de Combinatoire

http://www.mat.univie.ac.at/∼slc/.

[FSch73] Dominique Foata; Marcel-Paul Schützenberger. Nombres d’Euler et permutations alternantes, in J. N. Srivastava et al. (eds.), A Survey of Combinatorial Theory, North-Holland, Amsterdam, 1973, pp. 173–187.

[FSt74] Dominique Foata; Volker Strehl. Rearrangements of the symmetric group and enumerative properties of the tangent and secant numbers, Math. Z., vol. 137, 1974, p. 257–264.

[FSt76] Dominique Foata; Volker Strehl. Euler numbers and variations of permutations, in Colloquio Internazionale sulle Teorie Combinatorie, 1973, vol. I (Atti dei Convegni Lincei, 17, 119–131). Accademia Nazionale dei Lincei, 1976.

[GHZ11] Yoann Gelineau; Heesung Shin; Jiang Zeng. Bijections for Entringer families,

Europ. J. Combin., vol. 32, 2011, p. 100–115.

[He96] Gábor Hetyei. On the cd-variation polynomials of André and simsun permutations, Discrete Comput. Geom., vol. 16, 1996, p. 259–275.

[HR98] Gábor Hetyei; Ethan Reiner. Permutation trees and variation statistics, Europ. J. Combin., vol. 19, 1998, p. 847–866.

[Jo39] Charles Jordan. Calculus of Finite Differences. Röttig and Romwalter, Bu-

dapest, 1939.

[KPP94] A. G. Kuznetsov; I. M. Pak; A. E. Postnikov. Increasing trees and alternating permutations, Uspekhi Mat. Nauk, vol. 49, 1994, p. 79–110.

[MSY96] J. Millar; N. J. A. Sloane; N. E. Young. A new operation on sequences: the Boustrophedon transform, J. Combin. Theory Ser. A, vol. 17, 1996, p. 44–54.

[Ni23] Niels Nielsen. Traité élémentaire des nombres de Bernoulli. Paris, Gauthier-Villars, 1923.

[OEIS] OEIS Foundation. Sequence A008282, The On-Line Encyclopedia of Integer Sequences, 2015, http://oeis.org.

[Po89] Christiane Poupard. Deux propriétés des arbres binaires ordonnés stricts, Europ. J. Combin., vol. 10, 1989, p. 369–374.

[Pu93] Mark Purtill. André permutations, lexicographic shellability and the cd-index of

a convex polytope, Trans. Amer. Math. Soc., vol. 338, 1993, p. 77–104.

[Se1877] L. Seidel. Über eine einfache Entstehungsweise der Bernoullischen Zahlen und einiger verwandten Reihen, Sitzungsberichte der Münch. Akad. Math. Phys. Classe, 1877, pp. 157–187.

[St76] Richard P. Stanley. Binomial posets, Möbius inversion, and permutation enumeration, J. Combin. Theory Ser. A, vol. 20, 1976, p. 336–356.

[St94] Richard P. Stanley. Flag f-vectors and the cd-index, Math. Z., vol. 216, 1994, p. 483–499.

[St10] Richard P. Stanley. A survey of alternating permutations, in Combinatorics and graphs, 165–196, Contemp. Math., 531, Amer. Math. Soc. Providence, RI, 2010.

[Str74] Volker Strehl. Geometrische und arithmetische Eigenschaften von André-Poly-nomen, Ph. D. Thesis, Friedrich-Alexander-Universität Erlangen-Nürnberg, 1974.

[Vi80] Gérard Viennot. Une interprétation combinatoire des coefficients des développements en série entière des fonctions elliptiques de Jacobi, J. Combin. Theory, Series A, vol. 29, 1980, p. 121–133.

[Vi88] Xavier G. Viennot. Séries génératrices énumératives, chap. 3, 160 pp., 1988; notes of lectures given at the École Normale Supérieure Ulm (Paris), the UQAM (Montréal, Québec) and the University of Wuhan (China)

http://www.xavierviennot.org/xavier/cours.html.

Dominique Foata Institut Lothaire 1, rue Murner F-67000 Strasbourg, France

foata@unistra.fr

Guo-Niu Han

I.R.M.A. UMR 7501

Université de Strasbourg et CNRS 7, rue René-Descartes F-67084 Strasbourg, France

                       guoniu.han@unistra.fr