Dominique Foata

Guo-Niu Han

Tree Calculus for Bivariate Difference Equations

Keywords: Tree Calculus, partial difference equations, strictly ordered binary trees, end of minimal chain, parent maximum leaf, bivariate distributions, Poupard triangle, tangent numbers. Mathematics Subject Classifications. 05A15, 05A30, 11B68, 33B10

Following Poupard's study of strictly ordered binary trees with respect to two parameters, namely, "end of minimal chain" and "parent of maximum leaf" a true Tree Calculus is being developed to solve a partial difference equation system and then make a joint study of those two statistics. Their joint distribution is shown to be symmetric and to be expressed in the form of an explicit three-variable generating function.

Introduction

The triangle of numbers

f = f 0 (1) f 1 (1) f 1 (2) f 1 (3) f 2 (1) f 2 (2) f 2 (3) f 2 (4) f 2 (5) f 3 (1) f 3 (2) f 3 (3) f 3 (4) f 3 (5) f 3 (6) f 3 (7) f 4 (1) f 4 (2) f 4 (3) f 4 (4) f 4 (5) f 4 (6) f 4 (7) f 4 (8) f 4 (9)
= 1 0 1 0 0 1 2 1 0 0 4 8 10 8 4 0 0 34 68 94 104 94 68 34 0 [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF], f = (f n (m)) (n ≥ 0, 1 ≤ m ≤ 2n + 1) is the unique solution of the finite difference equation system

(1.1) ∆ 2 f n (m) + 2 f n-1 (m) = 0 (n ≥ 1, 1 ≤ m ≤ 2n -1),
where ∆ stands for the classical finite difference operator (see, e.g., [START_REF] Jordan | Calculus of Finite Differences. Röttig and Romwalter[END_REF])

∆f n (m) := f n (m + 1)f n (m), (1.2) so that

∆ 2 f n (m) = f n (m + 2) -2f n (m + 1) + f n (m), (1.3)
when taking f 0 (1) = 1; f n (1) = 0, and either f n (2) = m f n-1 (m) (n ≥ 1), or f n (2n + 1) = 0 (n ≥ 1) as initial values. Note that with the latter set of initial conditions it is immediately seen that the triangle f is symmetric with respect to the column f 0 (1) f 1 (2) f 2 (3) . . . f n (n + 1) . . .

Let tan u = n≥1 u 2n-1 (2n -1)! T 2n-1 (1.4) = u 1! 1 + u 3 3! 2 +
(•) := f n (1) + f n (2) + • • • + f n (2n + 1
) is equal to the integer T 2n+1 /2 n (n ≥ 0), that is, reporting to Table 1.1: 1, 1, 4, 34, 496,. . . Finally, on the set T 2n+1 of strictly ordered binary trees with (2n + 1) vertices (see Definition 1.2), she defines two statistics "eoc" ("end of minimal chain") and "pom" ("parent of the maximum leaf"), to show that both statistics "eoc" and "pom+1" are equally distributed on each set T 2n+1 , and furthermore, (1.5) #{t ∈ T 2n+1 : eoc(t) = k + 1} = #{t ∈ T 2n+1 : pom(t) = k} = f n (k) for all k; in particular, #T 2n+1 = T 2n+1 /2 n . Note that a combinatorial proof of the first identity in (1.5) has been given in [START_REF] Foata | Finite Difference Calculus for Alternating Permutations[END_REF].

It was then natural to see whether the joint distribution of the pair (eoc, pom) on each set T 2n+1 could be calculated, no longer by a onevariable system, such as (1.1), but by a system of partial finite difference equations (see equations (R 1), (R 2) below), verifying certain initial conditions. This is the purpose of the paper. To achieve this, we first introduce a sequence (M n = (f n (m, k)) of (2n) × (2n)-matrices (n ≥ 1) with nonnegative integral entries, called a Delta sequence, defined by such a system and prove that each entry f n (m, k) is equal to the number of trees t from T 2n+1 such that eoc(t) = m and pom(t) = k. We finally calculate the exponential generating function for the matrices M n .

For defining the Delta Sequence it is convenient to consider the following four triangles of each square {(m, k) : 1 ≤ m, k ≤ 2n}: L

(1) (1.7) They serve to define the recurrence relations:

n := {2 ≤ k + 1 ≤ m ≤ 2n -2}; L (2)
n := {4 ≤ k + 3 ≤ m ≤ 2n}; U (1) n := {2 ≤ m + 1 ≤ k ≤ 2n -2}; U (2) n := {4 ≤ m + 3 ≤ k ≤ 2n}. By convention, f n (m, k) := 0 if (m, k) ∈ [1, 2n] × [1, 2n]
∆ m 2 f n (m, k) + 2 f n-1 (m, k) = 0 ((m, k) ∈ L (1) n ); (R 1) ∆ k 2 f n (m, k) + 2 f n-1 (m, k) = 0 ((m, k) ∈ U (1) n ). (R 2)
Finally, the row and column sums of M n = (f n (m, k)) are denoted by

f n (m, •) := 1≤k≤2n f n (m, k); (1 ≤ m ≤ 2n); f n (•, k) := 1≤m≤2n f n (m, k) (1 ≤ k ≤ 2n).
Definition 1.1. A sequence of matrices (M n ) (n ≥ 1), where each matrix M n = (f n (m, k)) (1 ≤ k, m ≤ 2n) has nonnegative integral entries, having only 0's along its diagonal, and such that M 1 := 0 0 1 0 , is said to be a Delta Sequence, if for n ≥ 2 both recurrence relations (R 1) and (R 2) hold, together with the initial conditions: (I 1) for n ≥ 2 the (2n)-th column, Col 2n , of M n is the zero-column; its the (2n -1)-st column, Col 2n-1 , is equal to

f n-1 (1, •), f n-1 (2, •), . . . , f n-1 (2n -2, •), 0, 0,
when read from top to bottom.

(I 2) the (2n)-th row of M n is also equal to f n-1 (1, •), f n-1 (2, •), . . . , f n-1 (2n -2, •), 0, 0, when read from left to right; its (2n -1)-st row is equal to:

f n-1 (1, •) + f n-1 (•, 1), f n-1 (2, •) + f n-1 (•, 2), . . . , f n-1 (2n -3, •) + f n-1 (•, 2n -3), f n-1 (2n -2, •) + f n-1 (•, 2n -2), 0, 0, when read from left to right.

As shown in Section 2, conditions (R 1), (R 2), (I 1), (I 2) uniquely determine the Delta Sequence (M n ) (n ≥ 1), whose first values are reproduced in Fig. 2.1. As for the "labeled strictly ordered binary trees" and the statistics "eoc," "pom" their definitions are now given.

Definition 1.2. An n-labeled strictly ordered binary tree is defined by the following axioms:

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

(2) each node has no child (it is then called a leaf ), or two children, their order being immaterial (it is then called an internal node);

(3) when getting along each path from the root to each node, the node labels are in increasing order. Let T 2n+1 denote the set of all (2n + 1)labeled strictly ordered binary trees.

Let t ∈ T 2n+1 (n ≥ 1). If a node labeled a has two children labeled b and c, define min a := min{b, c}; if it has one child b, let min a := b. The minimal chain of t is defined to be the sequence a 1 → a 2 → a 3 → • • • → a j-1 → a j , with the following properties: (i) a 1 = 1 is the label of the root; (ii) for i = 1, 2, . . . , j -1 the (i + 1)-st term a i+1 is the label of an internal node and a i+1 = min a i ; (iii) a j is the node of a leaf. Define the "end of the minimal chain" of t to be eoc(t) := a j . If the leaf with the maximum label (2n + 1) is incident to a node labeled k, define its "parent of the maximum leaf" to be pom(t) := k.

7 8 5 9 4 3 6 2 1 ❅ ❅✥ ✥ ✥ ✥ ✥ ✥ ✥ ✥ ✁ ✁ ❆ ❆ ❆ ❆ ✁ ✁ Fig. 1.2.
Labeled strictly ordered binary tree.

For example, the minimal chain of the tree t displayed in Fig. 1.2 is 1 → 2 → 3 → 7, so that eoc(t) = 7 and the parent of its maximum leaf (equal to 2n + 1 = 9) is pom(t) = 4. The main results of this paper are the following theorems.

Theorem 1.1. Let (M n = (f n (m, k)) (n ≥ 1) be the Delta sequence, as introduced in Definition 1.1. Then, for all n ≥ 1 and

1 ≤ m, k ≤ 2n #{t ∈ T 2n+1 : eoc(t) = m, pom(t) = k} = f n (m, k). (1.9) In particular, m,k f n (m, k) = T 2n+1 /2 n (n ≥ 0). (1.10) Theorem 1.2. Let M n = (f n (m, k)) (1 ≤ m, k ≤ 2n) (n ≥ 1)
be the Delta sequence. Then, the matrices M n are symmetric with respect to their counter-diagonals:

(1.11) f n (m, k) = f n (2n + 1 -k, 2n + 1 -m) (1 ≤ k, m ≤ 2n).
Theorem 1.3. The triple exponential generating function for the lower triangles of the matrices M n is given by

(1.12) 2≤k+1≤m≤2n f n (m, k) x m-k-1 (m -k -1)! y k-1 (k -1)! z 2n-m (2n -m)! = cos( √ 2 x) + cos( √ 2 y) cos( √ 2 z) 2 cos 2 x + y + z √ 2 .
Theorem 1.4. The triple exponential generating function for the upper triangles of the matrices M n is given by

(1.13) 2≤m+1≤k≤2n-1 f n (m, k) x 2n-k (2n -k)! y k-m-1 (k -m -1)! z m-1 (m -1)! = sin( √ 2 x) sin( √ 2 z) 1 2 cos 2 x + y + z √ 2
.

Theorems 1.1 and 1.2 will be proved in Sections 3-7, where we develop a genuine Tree Calculus on the sequence (T 2n+1 ), which appears to be an alternative for the constructions of several combinatorial bijections. In Theorems 1.3 and 1.4 note that an adequate normalization for the threevariable series is to be found for getting such closed expressions for the generating functions for the f n (m, k)'s.

Delta and gamma sequences and organization of the paper

Go back to Definition 1.1 of the Delta Sequence. It is based on the two relations (R 1), (R 2) and the two initial conditions (I 1), (I 2). Those relations and conditions can be symbolized by the square in Fig. 2.1, as relation (R 1) (resp. (R 2)) acts on the entries of the lower (resp. upper) entries of the matrix M n , and initial conditions (I 1) and (I 2) refer to the last two columns Col 2n-1 , Col 2n and rows Row 2n-1 , Row 2n of M n , respectively. In Definition 1.1 of the Delta Sequence the entries of each matrix M n are derived from M n-1 by first applying rules (I 1) and (I 2) and letting the diagonal be null; then, starting from m = 1 up to m = 2n -3, for each k from 2n -3 down to m + 1, evaluate f n (m, k) with equation (R 2):

❅ ❅ ❅ ❅ ❅ ←→ ↓ ↑ Row 2n Row 2n-1 Col 2n-1 Col 2n (R 2) (R 1)
f n (m, k) -2f n (m, k + 1) + f n (m, k + 2) + 2f n-1 (m, k) = 0, the coefficients f n (m, k + 1), f n (m, k + 2) and f n-1 (m, k) being already calculated.
Exchanging the roles of m and k the upper entries are obtained by using equation (R 1). Accordingly, (R 1), (R 2), (I 1), (I 2) uniquely determine the Delta Sequence (M n ) (n ≥ 1).

Calculation of the first matrices

. First, f 1 (1, •) = 0, f 1 (2, •) = 1, so that M 2 =    0 ? 0 0 ? 0 1 0 1 1 0 0 0 1 0 0   
by rules (I 1) and (I 2). The remaining entries are obtained by rule (R 2):

f 2 (1, 2) -2f 2 (1, 3) + f 2 (1, 4) + 2f 1 (1, 2) = f 2 (1, 2) -2 × 0 + 0 + 2 × 0 = 0, so that f 2 (1, 2) = 0; then, by rule (R 1): f 2 (2, 1) -2f 2 (3, 1) + f 2 (4, 1) + 2f 1 (2, 1) = f 2 (2, 1) -2 × 1 + 0 + 2 × 1 = 0, so that f 2 (2, 1) = 0. Thus, M 2 =    0 0 0 0 0 0 1 0 1 1 0 0 0 1 0 0    and f 2 (1, •) = 0, f 2 (2, •) = 1, f 2 (3, •) = 2, f 2 (4, •) = 1. The next matrices are displayed in Fig. 1.2. M 3 =        0 0 0 0 0 0 0 0 1 2 1 0 1 1 0 4 2 0 2 3 4 0 1 0 1 3 3 1 0 0 0 1 2 1 0 0        M 4 =            0 0
0 0 0 0 0 0 0 0 4 8 10 8 4 0 4 4 0 16 20 16 8 0 8 12 16 0 28 20 10 0 10 18 24 28 0 16 8 0 8 18 24 24 16 0 4 0 4 12 18 18 12 4 0 0 0 4 8 10 8 4 0 0

           . M 5 =                0 0 0 0 0 0 0 0 0 0 0 0
               Fig. 2.2: the first matrices M n .
Other initial conditions could be stated; they will be mentioned in Section 9. At this point we just describe a second one, materialized by the square in Fig. 2.3 Definition 2.1. A sequence of matrices (M n ) (n ≥ 1), where each matrix M n = (f n (m, k)) (1 ≤ k, m ≤ 2n) has nonnegative integral entries, having only 0's along its diagonal, and such that M 1 := 0 0 1 0 , is said to be a Gamma Sequence, if for n ≥ 2 both recurrence relations

∆ m 2 f n (m, k) + 2 f n-1 (m, k -2) = 0 ((k, m) ∈ U (2) n ); (R 3) ∆ k 2 f n (m, k) + 2 f n-1 (m -2, k) = 0 ((k, m) ∈ L (2) n ); (R 4)
hold, together with the initial conditions:

(I 3) for n ≥ 2 the first row, Row 1 , is the zero-row; the second row, Row 2 , is equal to

0, f n-1 (1, •)(= 0), f n-1 (2, •), . . . , f n-1 (2n -2, •), f n-1 (2n -1, •)(= 0);
when read from left to right.

(I 4) the first column, Col 1 , of M n is also equal to 0, f n-1 (1, •)(= 0), f n-1 (2, •), . . . , f n-1 (2n -2, •), f n-1 (2n -1, •)(= 0)
when read from top to bottom; the second column, Col 2 , is equal to

0, 0, f n-1 (2, •) + f n-1 (1, •), f n-1 (3, •) + f n-1 (2, •), . . . f n-1 (2n -2, •) + f n-1 (2n -3, •), f n-1 (2n -2, •),
when read from left to right. Using the same reasoning as for Definition 1.1 it is seen that the Gamma Sequence is uniquely defined. The fact that Delta and Gamma Sequences are identical will be a consequence of the further theorems (cf. Section 6).

❅ ❅ ❅ ❅ ❅ ←→ ↓ ↑ (R 4) (R 3) Row 1 Row 2 Col 1 Col 2
Again, go back to Definition 1.1. Each tree from T 2n+1 has an odd number of vertices, i.e., (2n + 1), with n internal nodes and (n + 1) leaves. When giving an orientation (left or right) to each child of each of the n internal nodes, we generate 2 n planar strictly ordered binary trees (also called "arbres binaires croissants complets" by Viennot [START_REF] Xavier | Séries génératrices énumératives[END_REF]chap. 3,p. 111]). It is known that the latter are equidistributed with the alternating permutations of order (2n+1), so that their number is equal to the tangent number T 2n+1 , a result that goes back to Désiré André [An1879, An1881]. Accordingly,

(2.1) #T 2n+1 = T 2n+1 /2 n .
When dealing with those strictly ordered binary trees, we adopt the following notation and convention: for each triple (n, m, k) let T 2n+1,m,k (resp. T 2n+1,m,• , resp. T 2n+1,•,k ) denote the subset of T 2n+1 of all trees t such that eoc(t) = m and pom(t) = k (resp. eoc(t) = m, resp. pom(t) = k). By convention, designate those families and their cardinalities by the same symbol and also the matrix of the integers T 2n+1,m,k by Mat(T 2n+1 ). Our plan of action will be to show that the sequence (Mat(T 2n+1 )) (n ≥ 1) is identical to the Delta Sequence.

In Sections 3-6 it will be shown that, when replacing each f n (m, k) by T 2n+1,m,k the initial conditions (I 1) and (I 2), the two finite difference equations systems (R 1), (R 3), the two finite difference equations systems (R 2), (R 4) and the initial conditions (I 3) and (I 4)) hold. This will complete the proofs of Theorems 1.1 and 1.2, as done in Section 7. Further properties of the matrices Mat(T 2n+1 ) (and then matrices M n ) will be given in Section 8. Finally, several other equivalent definitions of the Delta sequence will be mentioned in Section 9. Finally, the calculation of the generating functions for the matrices M n is made in Section 10.

The initial conditions (I 1) and (I 2)

In this section and the next ones we make the convention that whenever a leaf is deleted from a tree, the edge linking the leaf to the tree is also deleted.

For verifying that the matrices Mat(T 2n+1 ) have only zero in their diagonals, it suffices to show that T 2n+1,m,m = ∅ (or is equal to 0 with our convention). This is true, because if t ∈ T 2n+1 and eoc(t) = pom(t) = m, the node (2n + 1) has a parent equal to m. Consequently, m cannot be the end of a minimal chain. Hence, the previous subset is empty.

Theorem 3.1. The initial conditions (I 1) and (I 2) hold for the matrices Mat(T 2n+1 ) when f n (m, •) and f n (•, k) are replaced by T 2n+1,m,• and T 2n+1,•,k , respectively.

Proof. (I 1) First, the (2n)-th column of the matrix Mat(T 2n+1 ) has zero entries only, as pom ≤ 2n -1. Next, each tree from T 2n+1,m,2n-1 (1 ≤ m ≤ 2n -2) must contain the subtree

❅ ❅ 2n 2n-1 2n+1
Hence, T 2n+1,2n-1,2n-1 is empty, for (2n -1), being an internal node, cannot be the end of the minimal chain. Also, T 2n+1,2n,2n-1 is empty, for the sibling of (2n -1) is necessarily less than (2n -1), so that the minimal chain cannot go through (2n -1) and reach (2n). Furthermore, T 2n+1,1,2n-1 = T 2n-1,1,• = 0, as eoc ≥ 2.

In the remaining cases, that is, 2 ≤ m ≤ 2n-2, removing the two leaves (2n), (2n + 1) transforms each tree from T 2n+1,m,2n-1 onto a tree from T 2n-1,m,• in a bijective manner. Such a transformation may be illustrated by the diagram:

❅ ❅ ❅ ❅ ❅ 1 2n-1 m • 2n 2n+1 → ❅ ❅ ❅ 1 2n-1 m •
Hence, the (2n -1)-st column of the matrix Mat(T 2n+1 ) reads:

(3.1)

T 2n-1,1,• , T 2n-1,2,• , . . . , T 2n-1,2n-2,• , 0, 0.
from top to bottom. (I 2) For the (2n)-th row of the matrix Mat(T 2n+1 ) note that

T 2n+1,2n,1 = 0 for n ≥ 2. When k ≥ 2 each tree from T 2n+1,2n,k must contain the subtree ❅ ❅ 2n • k 2n+1
By (I 1) we then have: T 2n+1,2n,2n-1 = T 2n+1,2n,2n = 0. For the remaining cases 2 ≤ k ≤ 2n -2 we can set up a bijection of T 2n+1,2n,k onto T 2n-1,k,• by removing the two leaves 2n and (2n + 1), as illustrated by the next diagram.

❅ ❅ ❅ ❅ ❅ 1 k • 2n 2n+1 → ❅ ❅ ❅ 1 k •
Note that the node k becomes the end of the minimal chain. Thus, the (2n)-th row of the matrix T 2n+1 is also equal to (3.1) read from left to right.

Finally, consider the (2n -1)-st row of T 2n+1 . In an obvious manner,

T 2n+1,2n-1,2n-1 = T 2n+1,2n-1,2n = 0 . When 1 ≤ k ≤ 2n -2, the trees from the sets T 2n+1,2n-1,k fall into two categories T I 2n+1,2n-1,k and T II 2n+1,2n-1,k .
In the first category the trees contain the subtree

❅ ❅ 2n+1 k • 2n-1 ; in the second one, the subtree ❅ ❅ 2n a 2n-1 • (a = k). First, note that T I 2n+1,2n-1,1 = T 2n-1,1,• = 0. When 2 ≤ k ≤ 2n -2
, removing the two leaves (2n + 1), (2n -1) and replacing the node label (2n) by (2n -1) maps T I 2n+1,2n-1,k onto T 2n-1,k,• in a bijective manner.

When 1 ≤ k ≤ 2n -2, removing the two leaves (2n), (2n -1), and replacing the node label (2n + 1) by (2n -1) maps T II 2n+1,2n-1,k onto T 2n-1,•,k in a bijective manner. Thus, the (2n -1)-st row of T 2n+1 reads

T 2n-1,1,• + T 2n-1,•,1 , T 2n-1,2,• + T 2n-1,•,2 , . . . , T 2n-1,2n-3,• + T 2n-1,•,2n-3 , T 2n-1,2n-2,• + T 2n-1,•,2n-2 , 0, 0.

Tree Calculus for the relations (R 1) and (R 3)

In the following Tree Calculus subtrees (possibly leaves) are indicated by the symbols " ," "▽", or " ." The end of the minimal chain in each tree is represented by a bullet "•." Letters occurring below or next to subtrees are labels of their roots. For instance, the symbols

❅ ❅ a • m b , [ ❅ ❅ a • m b , c ]
designate the families of all trees t from the underlying set T 2n+1 having a node labeled b [in short, a node b], parent of both a subtree of root a and the leaf m, which is also the end of the minimal chain; moreover, the symbol on the right has the further property that the node labeled c does not belong, either to the subtree of root b, or to the path going from root 1 to b. In the sequel, the letter "m" is always used to designate the end of the minimal chain, unless explicitly indicated by a letter next to •.

Our Tree Calculus consists of two steps: (a) decomposing the sets T 2n+1,m,k into smaller subsets by considering the mutual positions of the nodes m, (m+1), (m+2) (resp. k, (k+1), (k+2)); (b) setting up bijections between those subsets by a simple display of certain subtrees, as done in (4.1).

For instance, (4.1)

C 3 := ❅ ❅ ❅ • m m+1 m+2 and D 1 := ❅ ❅ ❅ ❅ m+2 • m m+1
may be regarded as two subsets of T 2n+1 . To each pair ( m+2 , ) there correspond a unique tree from C 3 and a unique tree from D 1 , as the nodes of " " are all greater than or equal to (m + 2). This clearly defines a bijection of C 3 onto D 1 .

Those two principles (a) and (b) will be applied in the proofs of the next two theorems 4.1 and 5.1.

Theorem 4.1. If (m, k) belongs to L (1) n ∪ U (2) n = {2 ≤ k + 1 ≤ m ≤ 2n -2} ∪ {4 ≤ m + 3 ≤ k ≤ 2n}, then ∆ m 2 T 2n+1,m,k + 2 ❅ ❅ m+1 m • m+2 = 0, (4.2)
with the understanding that the second term on the left-hand side represents twice the set of all trees from T 2n+1,m+1,k with the further property that m is the parent of both (m + 1) and (m + 2).

Proof. The decomposition

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

T 2n+1,m+1,k = ❅ ❅ m+1 m • + ❅ ❅ m+1 b • (b = m).
Under the transposition (m, m + 1) the node labeled

k remains unaffected, because k ≤ m -1 if (m, k) ∈ L (1) n and m + 3 ≤ k if (m, k) ∈ U (2)
n , so that the parent of (2n + 1) remains k. Thus, the transposition establishes a one-to-one correspondence between the two second terms. Hence,

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

A = ❅ ❅ ❅ • m+1 m+2 m + [ ❅ ❅ ❅ • m+1 m+2 , m] := A 1 + A 2 ; B = ❅ ❅ m+1 m • m+2 + ❅ ❅ ❅ ❅ • m+1 m+2 m + [ ❅ ❅ m+1 m+2 • , m] := B 1 + B 2 + B 3 ; C = ❅ ❅ m+1 m • m+2 + ❅ ❅ ❅ ❅ • m+1 m+2 m + ❅ ❅ ❅ • m m+1 m+2 + [ ❅ ❅ ❅ • m m+1 , m + 2] := C 1 + C 2 + C 3 + C 4 ; D = ❅ ❅ ❅ ❅ m+2 • m m+1 + [ ❅ ❅ m m+1 • , m + 2] := D 1 + D 2 .
The permutation m m+1 m+2 m+2 m m+1 establishes a one-to-one correspondence between A 2 and C 4 (resp. between B 3 and D 2 ). On the other hand, Corollary 4.2. The relations (R 1) and (R 3) hold for the matrices Mat(T 2n+1 ), that is,

A 1 = B 2 + C 2 = 2 B 2 ,
∆ m 2 T 2n+1,m,k + 2 T 2n-1,m,k = 0, if (m, k) ∈ L (1) n ; (4.3) ∆ m 2 T 2n+1,m,k + 2 T 2n-1,m,k-2 = 0, if (m, k) ∈ U (2)
n . (4.4) Proof. For (4.3) change the second term in (4.2) as follows: remove the two leaves (m + 1), (m + 2), and subtract 2 from all the remaining nodes greater than (m + 2): the term becomes T 2n-1,m,k , as the node (2n + 1) becomes (2n -1) and is still linked to k. For (4.4) do the same changes, but this time, as m + 3 ≤ k, the edge going from k to (2n + 1) becomes an edge going from (k -2) to (2n -1).

Tree Calculus for the relations

(R 2) and (R 4) Theorem 5.1. If (m, k) belongs to L (2) n ∪ U (1) n = {4 ≤ k + 3 ≤ m ≤ 2n} ∪ {2 ≤ m + 1 ≤ k ≤ 2n -2}, then ∆ k 2 T 2n+1,m,k + 2 [ ❅ ❅ ❅ k+1 k+2 2n+1 k , m] + 2 ❅ ❅ ❅ • m k+2 k+1 2n+1 k = 0, (5.1)
with the understanding that the second term on the left-hand side is twice the number of all trees from T 2n+1,m,k+1 with the further property that (k + 2) is a leaf incident to (k + 1), itself incident to k, the end m of the minimum chain being outside the subtree of root k.

Proof. First,

T 2n+1,m,k = [ ❅ ❅ k+1 2n+1 k , m] + [ ❅ ❅ 2n+1 k , m, k + 1] + ❅ ❅ k+1 2n+1 k • m + [ ❅ ❅ 2n+1 k • m , k + 1] := A 1 + A 2 + A 3 + A 4 ,
meaning that each tree from T 2n+1,m,k has one of the four forms: either k + 1 is incident to k, or not, and m is outside or not the subtree of root k; furthermore, the leaf m is the end of the minimal chain.

Using the same dichotomy,

T 2n+1,m,k+1 = [ ❅ ❅ ❅ k+1 2n+1 k , m] + [ ❅ ❅ 2n+1 k+1 , m, k] + ❅ ❅ ❅ • m k+1 2n+1 k + [ ❅ ❅ 2n+1 k+1 • m
, k]

:= B 1 + B 2 + B 3 + B 4 .
Consider the subsets

A ′ 4 := ❅ ❅ ❅ • m k+1 k 2n+1 of A 4 and B ′ 2 := ❅ ❅ ❅ k k+1 2n+1 • m of B 2 . The transposition (k, k + 1) maps A 4 \ A ′ 4 onto B 4 and A 2 onto B 2 \ B ′ 2 in a bijective manner.
Hence,

T 2n+1,m,k+1 -T 2n+1,m,k = (B 1 -A 1 ) + ((B 2 -B ′ 2 -A 2 ) + B ′ 2 ) + (B 3 -A 3 ) + (B 4 -(A 4 -A ′ 4 ) -A ′ 4 ) = B 1 -A 1 + B ′ 2 + B 3 -A 3 -A ′ 4 = [ ❅ ❅ ❅ k+1 2n+1 k , m] -[ ❅ ❅ k+1 2n+1 k , m] + ❅ ❅ ❅ k k+1 2n+1 • m + ❅ ❅ ❅ • m k+1 2n+1 k - ❅ ❅ k+1 2n+1 k • m - ❅ ❅ ❅ • m k+1 k 2n+1 ;
and also

T 2n+1,m,k+2 -T 2n+1,m,k+1 = [ ❅ ❅ ❅ k+2 2n+1 k+1 , m] -[ ❅ ❅ k+2 2n+1 k+1 , m] + ❅ ❅ ❅ k+1 k+2 2n+1 • m + ❅ ❅ ❅ • m k+2 2n+1 k+1 - ❅ ❅ k+2 2n+1 k+1 • m - ❅ ❅ ❅ • m k+2 k+1 2n+1 := D 1 -C 1 + D ′ 2 + D 3 -C 3 -C ′ 4 .
Thus,

∆ k 2 T 2n+1,m,k = T 2n+1,m,k+2 -T 2n+1,m,k+1 -T 2n+1,m,k+1 -T 2n+1,m,k = D 1 -C 1 + D ′ 2 + D 3 -C 3 -C ′ 4 -B 1 + A 1 -B ′ 2 -B 3 + A 3 + A ′ 4 .
The further decompositions of the components of the previous sum depend on the mutual positions of the nodes k, (k + 1), (k + 2). First, evaluate the subsum: S 1 := D 1 -C 1 -B 1 + A 1 using the decompositions:

D 1 = [ ❅ ❅ ❅ k+2 2n+1 k+1 , m] = [ ❅ ❅ ❅ k+2 2n+1 k+1 , m, k ] + [ ❅ ❅ ❅ ❅ ❅ k+2 2n+1 k+1 ▽ k , m] := D 1,1 + D 1,2 ; C 1 = [ ❅ ❅ k+2 2n+1 k+1 , m] = [ ❅ ❅ k+2 2n+1 k+1 , m, k ] + [ ❅ ❅ ❅ k+1 k+2 2n+1 k , m] := C 1,1 + C 1,2 ; B 1 = [ ❅ ❅ ❅ k+1 2n+1 k , m] = [ ❅ ❅ ❅ k+1 2n+1 k , m, k + 2] + [ ❅ ❅ ❅ k+1 k+2 2n+1 k , m] + [ ❅ ❅ ❅ ❅ ❅ ▽ k+2 k+1 2n+1 k , m] + [ ❅ ❅ ❅ k+1 2n+1 k k+2 , m] + [ ❅ ❅ ❅ ❅ ❅ k+2 k+1 2n+1 k ▽ , m] := B 1,1 + B 1,2 + B 1,3 + B 1,4 + B 1,5 ; A 1 = [ ❅ ❅ k+1 2n+1 k , m] = [ ❅ ❅ k+1 2n+1 k , m, k + 2 ] + [ ❅ ❅ ❅ k+1 k+2 k 2n+1 , m] := A 1,1 + A 1,2 . Also, let D ′ 1,1 := ❅ ❅ ❅ ❅ ❅ k+2 2n+1 k+1 ▽ • m k ; C ′ 1,1 := ❅ ❅ ❅ ▽ • m k+1 k+2 2n+1 k . The permutation k k+1 k+2 k+2 k k+1 maps D 1,1 \ D ′ 1,1 onto B 1,1 and C 1,1 \ C ′ 1,1 onto A 1,1 . Hence, D 1,1 = B 1,1 + D ′ 1,1 , C 1,1 = A 1,1 + C ′ 1,1 . Moreover, D 1,2 = 2 B 1,3 , C 1,2 = A 1,2 , B 1,2 = B 1,4 , B 1,3 = B 1,5 . Altogether, S 1 = D 1 -C 1 -B 1 + A 1 = (B 1,1 + D ′ 1,1 + 2 B 1,3 ) -(A 1,1 + C ′ 1,1 + A 1,2 ) - (B 1,1 + B 1,2 + B 1,3 + B 1,2 + B 1,3 ) + (A 1,1 + A 1,2 ). Thus, (5.2) S 1 = -2 B 1,2 + D ′ 1,1 -C ′ 1,1 .
Next, evaluate the sum

S 2 := D ′ 2 + D 3 -C 3 -C ′ 4 -B ′ 2 -B 3 + A 3 + A ′ 4
by decomposing each of its components. We have:

D ′ 2 = ❅ ❅ ❅ k+1 k+2 2n+1 • m = [ ❅ ❅ ❅ k+1 k+2 2n+1 • m , k] + ❅ ❅ ❅ k+1 k+2 2n+1 k • m := D ′ 2,1 + D ′ 2,2 ; D 3 = ❅ ❅ ❅ • m k+2 2n+1 k+1 = [ ❅ ❅ ❅ • m k+2 2n+1 k+1 , k] + ❅ ❅ ❅ ❅ ❅ • m k+2 2n+1 k+1 ▽ k := D 3,1 + D 3,2 ; C 3 = ❅ ❅ k+2 2n+1 k+1 • m = [ ❅ ❅ k+2 2n+1 k+1 • m , k] + ❅ ❅ ❅ • m k+1 k+2 2n+1 k := C 3,1 + C 3,2 ; C ′ 4 = ❅ ❅ ❅ • m k+2 k+1 2n+1 = [ ❅ ❅ ❅ • m k+2 k+1 2n+1 , k] + ❅ ❅ ❅ • m k+2 k+1 2n+1 k + ❅ ❅ ❅ ❅ ❅ • m k+2 k+1 2n+1 k ▽ := C ′ 4,1 + C ′ 4,2 + C ′ 4,3 ; B ′ 2 = ❅ ❅ ❅ k k+1 2n+1 • m = [ ❅ ❅ ❅ k k+1 2n+1 • m , k + 2] + ❅ ❅ ❅ k k+1 k+2 2n+1 • m + ❅ ❅ ❅ ❅ ❅ k k+1 2n+1 ▽ • m k+2 := B ′ 2,1 + B ′ 2,2 + B ′ 2,3 ; B 3 = ❅ ❅ ❅ • m k+1 2n+1 k = [ ❅ ❅ ❅ • m k+1 2n+1 k , k + 2] + ❅ ❅ ❅ • m k+1 k+2 2n+1 k + ❅ ❅ ❅ • m k+2 k+1 2n+1 k + ❅ ❅ ❅ ❅ ❅ • m k+2 k+1 2n+1 k ▽ := B 3,1 + B 3,2 + B 3,3 + B 3,4 ; A 3 = ❅ ❅ k+1 2n+1 k • m = [ ❅ ❅ k+1 2n+1 k • m , k + 2] + ❅ ❅ ❅ • m 2n+1 k+1 k+2 k := A 3,1 + A 3,2 ; A ′ 4 = ❅ ❅ ❅ • m k+1 k 2n+1 = [ ❅ ❅ ❅ • m k+1 k 2n+1 , k + 2] + ❅ ❅ ❅ • m k+1 k k+2 2n+1 + ❅ ❅ ❅ ❅ ❅ • m k+1 k 2n+1 ▽ k+2 := A ′ 4,1 + A ′ 4,2 + A ′ 4,3
. Within the sum S 2 there are numerous cancellations we now describe.

(a) Components of the form

[t, k] or [t, k + 2],
where t is a subtree, whose root is labeled. There are four of them: D 3,1 , -C 3,1 , -B 3,1 , A 3,1 . Consider the subsets:

B 3,1,1 := ❅ ❅ ❅ ❅ ❅ • m k+1 2n+1 k ▽ k+2 ; A 3,1,1 := ❅ ❅ ❅ • m k k+1 2n+1 ▽ k+2 ; of B 3,1 and A 3,1 , respectively. The permutation k k+1 k+2 k+2 k k+1 maps D 3,1 onto B 3,1 \ B 3,1,1 and C 3,1 onto A 3,1 \ A 3,1,1 . Hence, D 3,1 -C 3,1 -B 3,1 + A 3,1 = (B 3,1 -B 3,1,1 ) -(A 3,1 -A 3,1,1 ) -B 3,1 + A 3,1 = -B 3,1,1 + A 3,1,1 . (b) Components of the form [t, k] or [t, k + 2],
where t is a subtree, whose root is not labeled. There are four of them:

D ′ 2,1 , -C ′ 4,1 , -B ′ 2,1 , A ′ 4,1 . Again, the permutation k k+1 k+2 k+2 k k+1 maps D ′ 2,1 onto B ′ 2,1 , and C ′ 4,1 onto A ′ 4,1 . Hence, D ′ 2,1 -B ′ 2,1 = -C ′ 4,1 + A ′ 4,1 = 0.
Their sum vanish.

(c) Components represented by a tree t, whose root is unlabeled. There are four of them:

-B ′ 2,2 , -B ′ 2,3 , -A ′ 4,2 , A ′ 4,3 . As B ′ 2,2 = A ′ 4,2 , the contribution of those components to S 2 is then -B ′ 2,3 + A ′ 4,3 . (d)
Components represented by a tree t, whose root is labeled. There are nine of them:

D ′ 2,2 , D 3,2 , -C 3,2 , -C ′ 4,2 , -C ′ 4,3 -B 3,2 , -B 3,3 , -B 3,4 , A 3,2
. By simply comparing the subtree contents we have:

D ′ 2,2 -C 3,2 = -B 3,2 + A 3,2 = 0, D 3,2 -(C ′ 4,3 + B 3,4 ) = 0 and C ′ 4,2 = B 3,3 . The contribution of those terms is then -2 C ′ 4,2 . Hence, S 1 +S 2 = (-2 B 1,2 +D ′ 1,1 -C ′ 1,1 )+ (-B 3,1,1 +A 3,1,1 )+(-B ′ 2,3 + A ′ 4,3 ) + (-2 C ′ 4,2 ) . As D ′ 1,1 = B ′ 2,3 , C ′ 1,1 = A 3,1,1 and B 3,1,1 = A ′ 4,3 , we get S 1 + S 2 = -2 B 1,2 -2 C ′ 4,2 , that is, ∆ k 2 T 2n+1,m,k -2 [ ❅ ❅ ❅ k+1 k+2 2n+1 k , m] -2 ❅ ❅ ❅ • m k+2 k+1 2n+1 k .
Corollary 5.2. The relations (R 2) and (R 4) hold for the matrices Mat(T 2n+1 ), that is,

∆ k 2 T 2n+1,m,k + 2 T 2n-1,m-2,k = 0, if (m, k) ∈ L (2) n ; (5.3) ∆ k 2 T 2n+1,m,k + 2 T 2n-1,m,k = 0, if (m, k) ∈ U (1) n . (5.
n , the third term of (5.1) vanishes and the second one is in bijection with 2[

❅ ❅ 2n-1 k , m], equal to 2 T 2n-1,m,k .
6. The initial conditions (I 3) and (I 4) Property 6.1. Initial conditions (I 3) and (I 4) hold for the matrices Mat(T 2n+1 ).

Proof. (I 3) The first row of each matrix Mat(T 2n+1 ) is obviously the zero-row, as 1 can never be the end of the minimal chain. For the second row note that for n ≥ 2 the set T 2n+1,2,k is empty when k = 2 or 2n. Also the set T 2n+1,2,1 is empty, for 2 and (2n + 1) can be both children of the root only when n = 1.

Let 3 ≤ k ≤ 2n -1. As illustrated by the diagram ❅ ❅ ❅ ❅ ❅ ❅ • 1 k 3 2 2n+1 → ❅ ❅ ❅ ❅ 1 2n-1 k-2
each tree from T 2n+1,2,k is transformed into a tree from T 2n-1,•,k-2 by deleting the two nodes 2 and 1 and reducing the remaining nodes by 2. This transformation is obviously a bijection. Thus, T 2n+1,2,k = T 2n-1,•,k-2 for 3 ≤ k ≤ 2n -1. The second row of Mat(T 2n+1 ) is then equal to the sequence (6.1) 0, 0, T 2n-1,•,1 , T 2n-1,•,2 , . . . , T 2n-1,•,2n-3 , T 2n-1,•,2n-2 (= 0); which is also equal to (6.2) 0, T 2n-1,1,• (= 0), T 2n-1,2,• , . . . , T 2n-1,2n-2,• , 0, by Poupard's result (1.5) (also by our combinatorial proof in [START_REF] Foata | Finite Difference Calculus for Alternating Permutations[END_REF] mentioned in the Introduction).

(I 4) The set T 2n+1,m,1 is empty when m = 1, 2 or 2n. When 3

≤ m ≤ 2n -1 the diagram ❅ ❅ ❅ ❅ • 1 m 2 2n+1 → ❅ ❅ 1 m-1
• serves to illustrate the transformation that maps each tree from T 2n+1,m,1 onto a tree from T 2n-1,m-1,• , by deleting the two nodes (2n +1) and 1, and reducing the remaining nodes by 1. Thus, the first column of M n is equal to sequence (6.2), when read from top to bottom.

For the second column we first note that T 2n+1,m,2 is empty when m = 1, 2 and n ≥ 2. When m = 3, the mapping

❅ ❅ ❅ ❅ • 1 2 3 2n+1 → ❅ ❅ 1 2n+1
shows that T 2n+1,3,2 is in bijection with T 2n-1,•,1 = T 2n-1,2,• . When m = 4, the following decomposition prevails

T 2n+1,4,2 = ❅ ❅ ❅ ❅ ❅ ❅ • 1 4 2 3 2n+1 + ❅ ❅ ❅ ❅ • 1 2 4 2n+1 3
the two sets on the right-hand side being in bijection, respectively, with

= ❅ ❅ ❅ ❅ • 1 2 3 + ❅ ❅ 1 2 • 3 , that is, = T 2n-1,3,• + T 2n-1,2,• .
To prove the identity T 2n+1,m,2 = T 2n-1,m-1,• + T 2n-1,m-2,• = T 2n+1,m,1 + T 2n+1,m-1,1 (by (6.2) and (I 4)) for 5 ≤ m ≤ 2n proceed by induction on m using relation (R 1) already proved in (4.3). Write

T 2n+1,m,2 = 2 T 2n+1,m-1,2 -T 2n+1,m-2,2 -2 T 2n-1,m-2,2 [by (4.3)] 2 T 2n+1,m-1,2 = 2 T 2n+1,m-1,1 + 2 T 2n+1,m-2,1 [by induction on m] -T 2n+1,m-2,2 = -T 2n+1,m-2,1 -T 2n+1,m-3,1 [by induction on m] -2 T 2n-1,m-2,2 = -2 T 2n-1,m-2,1 -2 T 2n-1,m-3,1 [by induction on n and m] 2 T 2n+1,m-1,1 -T 2n+1,m-2,1 -2 T 2n-1,m-2,1 = T 2n+1,m,1 [by (4.3)] 2 T 2n+1,m-2,1 -T 2n+1,m-3,1 -2 T 2n-1,m-3,1 = T 2n+1,m-1,1 .[by (4.3)]
By summing those six equations we get T 2n+1,m,2 = T 2n+1,m,1 + T 2n+1,m-1,1 , also equal to T 2n-1,m-1,• + T 2n-1,m-2,• by (6.2).

Remark. It would be interesting to make up a proof of Property 6.1 that would have no recourse to a recurrence argument for m ≥ 5 as above.

Proofs of Theorems 1.1 and 1.2

Taking Theorem 2.1, Corollaries 4.2 and 5.2, Property 6.1 into account we conclude that the sequence of matrices Mat(T 2n+1 ) is both a Delta and a Gamma sequence. Those sequences are then identical and we may write

(7.1) f n (m, k) = T 2n+1,m,k
for all n, m, k. This completes the proof of Theorem 1.1.

We now exploit the properties of the strictly ordered binary trees to prove that the matrices M n are symmetric with respect to their counterdiagonals (Theorem 1.2). First, the symmetry property is banal for M 1 , M 2 . For n ≥ 3 consider the NE-and SW-corners

f n (1, 2n -1) f n (1, 2n) f n (2, 2n -1) f n (2, n) = 0 0 f n (2, 2n -1) 0 f n (2n -1, 1) f n (2n -1, 2) f n (2n, 1) f n (2n, 2) = f n (2n -1, 1) f n (2n -1, 2) 0 f n (2n, 2)
of the matrix M n . As f n (2n-1, 1) = f n (2n, 2) = T 2n-3 = T 2n-3 /2 n-2 (by combining (1.11), (I 2), (I 3), (6.1) and (6.2)), both corners are symmetric with respect to their counter-diagonals [in short, counter-symmetric].

Let us prove that the upper part of the matrix M n is counter-symmetric and for i = 1, 2, . . . , n -1 adopt the notation: Row i = {(i, i + 1), (i, i + 2), . . . , (i, 2ni), (i, 2ni + 1)}; Col 2n-i+1 = {(i, 2ni + 1), (i + 1, 2ni + 1), . . . , (2ni -1, 2ni + 1), (2ni, 2ni + 1)}.

Note that Row i and Col 2n-i+1 have the cell (i, 2ni + 1), belonging to the counter-diagonal, in common. There is nothing to prove for the pairs (m, k) along the counter-diagonal and also for the entries from Row 1 and Col 2n , which are all zero. Let (m 0 , k 0 ) belong to Row j for some j such that 2 ≤ j ≤ n -1. Further, assume that (1.11) holds for all (m, k) ∈ Row 1 ∪ • • • ∪ Row j-1 and all (m, k) ∈ Row j lying on the right of (m 0 , k 0 ), not including (m 0 , k 0 ), that is, m = j and k > k 0 . By symmetry, (1.11) also holds for all (m, k) ∈ Col 2n ∪ • • • ∪ Col 2n-j+2 and all (m, k) ∈ Col 2n-j+1 lying above (2n + 1k 0 , 2n + 1m 0 ) not including the latter pair. Now, the following relations hold:

f n (m 0 , k 0 ) = 2f n (m 0 , k 0 + 1) -f n (m 0 , k 0 + 2) -2 f n-1 (m 0 , k 0 ) [by (R 2)] f n-1 (m 0 , k 0 ) = f n-1 (2n -1 -k 0 , 2n -1 -m 0 ), [by induction on n] f n (m 0 , k 0 + 1) = f n (2n -k 0 , 2n + 1 -m 0 ), f n (m 0 , k 0 +2) = f n (2n-1-k 0 , 2n+1-m 0 ).[

both by the local induction]

Therefore,

f n (m 0 , k 0 ) -2 f n (2n -k 0 , 2n + 1 -m 0 ) + f n (2n -1 -k 0 , 2n + 1 -m 0 ) + 2 f n-1 (2n -1 -k 0 , 2n -1 -m 0 ) = 0.
But by (R 3) written at (m, k) = (2n -1k 0 , 2n + 1m 0 ) we have:

f n (2n -1 -k 0 , 2n + 1 -m 0 ) -2 f n (2n -k 0 , 2n + 1 -m 0 ) -f n (2n -k 0 + 1, 2n + 1 -m 0 ) + 2 f n-1 (2n -1 -k 0 , 2n -1 -m 0 ) = 0.
By comparing the last two equations we conclude that

f n (m 0 , k 0 ) = f n (2n -k 0 + 1, 2n + 1 -m 0 ),
which means that (1.11) now holds for (m, k) = (m 0 , k 0 ).

For the entries of M n lying below the diagonal we proceed in the same manner and adopt the notation:

Row 2n+1-i = {(2n + 1 -i, i), . . . , (2n + 1 -i, 2n -i)}; Col i = {(i + 1, i), (i + 2, i), . . . , (2n + 1 -i, i)};
for i = 1, 2, . . . , n-1. Again, Row 2n+1-i and Col i have the cell (2n+1-i, i) in common. Let (m 0 , k 0 ) belong to Col j for some j such that 1 ≤ j ≤ n -1. Further, assume that (1.11) holds for all (m, k)

∈ Col 1 ∪ • • • ∪ Col j-1
and all (m, k) ∈ Col j lying below (m 0 , k 0 ), not including (m 0 , k 0 ), that is, m > m 0 and k = k 0 . By symmetry, (1.11) also holds for all (m, k) ∈ Row 2n ∪ • • • ∪ Row 2n-j+2 and all (m, k) ∈ Row 2n+1-j lying to the left of (2n + 1k 0 , 2n + 1m 0 ) not including the latter pair. Now, the following relations hold:

f n (m 0 , k 0 ) = 2f n (m 0 + 1, k 0 ) -f n (m 0 + 2, k 0 ) -2 f n-1 (m 0 , k 0 ), [by (R 1)], f n-1 (m 0 , k 0 ) = f n-1 (2n -1 -k 0 , 2n -1 -m 0 ), [by induction on n], f n (m 0 + 1, k 0 ) = f n (2n + 1 -k 0 , 2n -m 0 ), f n (m 0 + 2, k 0 ) = f n (2n + 1 -k 0 , 2n -1 -m 0 ), [by the local induction]. Therefore, f n (m 0 , k 0 ) = 2 f n (2n + 1 -k 0 , 2n -m 0 ) -f n (2n + 1 -k 0 , 2n -1 -m 0 ) -2 f n-1 (2n -1 -k 0 , 2n -1 -m 0 ).
But by (R 4) written at (m, k) = (2n + 1k 0 , 2n -1m 0 ) we have:

f n (2n + 1 -k 0 , 2n -1 -m 0 ) = 2 f n (2n + 1 -k 0 , 2n -m 0 ) -f n (2n + 1 -k 0 , 2n + 1 -m 0 ) -2 f n-1 (2n -1 -k 0 , 2n -1 -m 0 ).
By comparing the last two equations we conclude that

f 2n+1 (m 0 , k 0 ) = f 2n+1 (2n + 1 -k 0 , 2n + 1 -m 0 )), which means that (1.11) now holds for (m, k) = (m 0 , k 0 ).

Define (7.2)

Eoc(t) := eoc(t), but Pom(t) := 2n + 1pom(t).

Theorem 7.2. Let T 2n+1 (x, y) := t∈T 2n+1

x Eoc(t) y Pom(t) be the generating polynomial for the set T 2n+1 by the pair of statistics (Eoc, Pom). Then,

(7.3) T 2n+1 (x, y) = T 2n+1 (y, x).
Proof. This is a simple consequence of Theorem 1.2: let g n (m, k) := #{Eoc = m, Pom = k}. Then,

g n (m, k) = #{eoc = m, pom = 2n + 1 -k} = f n (m, 2n + 1 -k) = f n (k, 2n + 1 -m) [by (1.11)] = g n (k, m). Thus, T 2n+1 (x, y) = t∈T 2n+1 x Eoc(t) y Pom(t) = m,k g n (m, k)x m y k = m,k g n (k, m)x m y k = T 2n+1 (y, x).

Further properties

Other properties of the Delta Sequence can be obtained by having a further look at the geometry of the strictly ordered binary trees. The suband superdiagonals of the matrices M n for n = 2, 3, 4, 5 are equal, as can be seen in Fig. 2.2. For an arbitrary n ≥ 2 we have the following.

Property 8.1. Sub-and super diagonals are equal:

(8.1) f n (k + 1, k) = f n (k, k + 1) (n ≥ 2; 1 ≤ k ≤ 2n -1).
Proof. First, note that k and (k + 1) can be siblings in tree from T 2n+1,k,k+1 , but never in a tree from T 2n+1,k+1,k . Second, k can be parent of (k + 1) in a tree from the latter set, but never in a tree from the former one. Also, f n (2, 1) = f n (1, 2) = 0 for n ≥ 2 and for k ≥ 2 we have the decompositions:

f n (k, k + 1) = ❅ ❅ ❅ 2n+1 k+1 • k + [ ❅ ❅ ❅ 2n+1 k+1 , • k ]; f n (k + 1, k) = ❅ ❅ ❅ • 2n+1 k k+1 + [ ❅ ❅ ❅ 2n+1 k , • (k + 1) ].
The first terms in the previous two equations are in bijection, as well as the second ones, the notation "• k" meaning that k is the end of the minimal chain, following our convention on Tree Calculus (cf. Section 4).

Property 8.2. We have the crossing equalities:

(8.2) f n (k + 1, k -1) + f n (k -1, k + 1) = f n (k + 1, k) + f n (k -1, k) = f n (k, k + 1) + f n (k, k -1) (2 ≤ k ≤ 2n -1).
As can be seen in Fig. 2.2, the involved entries in the first identities are located on the four bullets drawn in the following diagram.

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

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

A 1 = C 1 , A 2 = C 3 , A 3 = D 4 , A 4 = D 3 , 2 A 5 = D 5 ; B 1 = D 1 , B 3 = D 2 , B 5 = C 5 . Moreover, B 4 -C 2 = ❅ ❅ ❅ ❅ ❅ k+1 • k k-1 2n+1 = D 5 = 2 A 5; C 4 -B 2 = ❅ ❅ ❅ • 2n+1 k-1 k+1 k = A 5 . Altogether, i (A i + B i ) -i (C i + D i ) = (B 4 -C 2 ) -(C 4 -B 2 ) + (A 5 - D 5 ) = 2 A 5 -A 5 + (A 5 -2 A 5 ) = 0.
Property 8.3. The row sums f n (m, •) form a Poupard Triangle, the initial conditions being:

f 0 (1, •) = 1, f n (1, •) = 0 and f n (2, •) = 2 m f n-1 (m, •) (n ≥ 1)
; and the finite difference system:

(8.3) ∆ m 2 f n (m, •) + 2 f n-1 (m, •) = 0 (1 ≤ m ≤ 2n -1).
The column sums f n (•, k) form a Poupard Triangle, the initial conditions being:

f 0 (•, 0) = 1, f n (•, 0) = 0 and f n (•, 1) = 2 k f n-1 (•, k) (n ≥ 1);
and the finite difference system:

(8.4) ∆ k 2 f n (•, k) + 2 f n-1 (•, k) = 0 (0 ≤ k ≤ 2n -2).
There are several proofs of this Property. First, the methods developed in Section 4 can be readapted by disregarding the conditions involving the pom-statistic. Here, we simply work out a specialization of the recurrence relations (R 1)-(R 4), that makes use of the previous two properties. Besides, we only prove the first part of the property that deals with the row sums.

Proof. For 1 ≤ m ≤ 2n -2 we have:

∆ m 2 f n (m, •) = 1≤k≤2n ∆ m 2 f n (m, k) = 1≤k≤m-1 ∆ m 2 f n (m, k) + ∆ m 2 (f n (m, m) + f n (m, m + 1) + f n (m, m + 2)) + m+3≤k≤2n ∆ m 2 f n (m, k) = 1≤k≤m-1 -2f n-1 (m, k) + f n (m, m) -2f n (m + 1, m) + f n (m + 2, m) + f n (m, m + 1) -2f n (m + 1, m + 1) + f n (m + 2, m + 1) + f n (m, m + 2) -2f n (m + 1, m + 2) + f n (m + 2, m + 2) + m+3≤k≤2n -2f n-1 (m, k -2).
In the previous sum the diagonal terms vanish. Also,

f n (m + 1, m) = f n (m, m + 1), f n (m + 2, m + 1) = f n (m + 1, m + 2) by (8.

1). The sum of the nine intermediate terms becomes

: -f n (m + 1, m) + f n (m + 2, m) - f n (m + 1, m + 2) + f n (m, m + 2), which is 0 by (8.2). Hence, ∆ m 2 f n (m, •) = -2 1≤k≤m-1 f n-1 (m, k) -2 m+1≤k≤2n-2 f n-1 (m, k) = -2f n-1 (m, •).
On the other hand, by (I 2) and (1.10),

f n (2n -1, •) = 1≤k≤2n f n (2n -1, k) = 1≤k≤2n-2 (f n-1 (k, •) + f n-1 (•, k)) = 2 f n-1 (•, •) := 2 #T 2n-1 = 2 T 2n-1 /2 n-1 ; f n (2n, •) = 1≤k≤2n f n (2n, k) = 1≤k≤2n-2 f n-1 (k, •) = f n-1 (•, •) = #T 2n-1 = T 2n-1 /2 n-1 ; f n (2n + 1, •) = 0.
The last three evaluations imply that ∆

m 2 f n (2n -1, •) = -2 f n-1 (2n - 1, •) = 0.

Other equivalent definitions for the Delta sequence

Definitions 1.1 and 2.1 have been shown to be equivalent to characterize a Delta Sequence. Other combinations of the recurrence relations (R 1)-(R 4), together with the initial conditions (I 1)-(I 4), can be used. We describe them by means of squares and arrows, as was done in Fig. 2.1 and 2.3 (see Fig. 9.1 (a) and (b)). Moreover, further initial conditions can be introduced; they are denoted by (SW ), (NE), as they refer only to the South-West and North-East corners of the matrices:

f n (2n -1, 1) f n (2n -1, 2) f n (2n, 1) f n (2n, 2) = f n-1 (•, 1) f n-1 (2, •) + f n-1 (•, 2) 0 f n-1 (•, 1) ; (SW ) f n (1, 2n -1) f n (1, 2n) f n (2, 2n -1) f n (2, n) = 0 0 f n-1 (2, •) 0 = 0 0 f n-1 (2n -2, •) 0 . (NE)
When one of those two conditions (SW ), (NE) is involved, two recurrence relations among (R 1)-(R 4) are needed to build up an equivalent definition. In Fig. 9.1 (c) for instance, (R 1) and (R 4) are to be associated with (SW ). We then get five further equivalent definitions (Fig. 9.1 (c-g)): We do not reproduce any proofs for those equivalences, but point out the fact that our Tree Calculus requires that each initial condition be combinatorially interpreted, as was done in Sections 2 and 5. 10. Generating functions for the Delta sequence 1. Poupard matrices. Let G = (g i,j ) (i ≥ 0, j ≥ 0) be an infinite matrix with nonnegative integral entries. Say that G is a Poupard matrix, if for every i ≥ 0, j ≥ 0 the following identity holds: (10.1) g i,j+2 -2 g i+1,j+1 + g i+2,j + 2 g i,j = 0.

❅ ❅ ❅ ❅ ❅ ↓ ↑ ↓ ↑ Row 2n-1 Row 2n Row 1 Row 2 (R 1) (R 3) (a) ❅ ❅ ❅ ❅ ❅ ←→ (R 2) ←→ (R 4) Col 2n-1 Col 2n Col 1 Col 2 (b) ❅ ❅ ❅ ❅ ❅ ←→ ↓ ↑ ↓ ↑ (SW ) (R 4) (R 1) (R 3) (c) ❅ ❅ ❅ ❅ ❅ ←→ ↓ ↑ (SW ) (R 4) (R 1) (R 2) ←→ Col 2n-1 Col 2n (d) ❅ ❅ ❅ ❅ ❅ ↓ ↑ ↓ ↑ (NE) (R 3) (R 1) (R 2) ←→ Row 2n-1 Row 2n (e) (R 4) ❅ ❅ ❅ ❅ ❅ ←→ ↓ ↑ (NE) (R 3) (R 2) ←→ Col 1 Col 2 (f) ❅ ❅ ❅ ❅ ❅ ←→ ↓ ↑ (SW ) (R 4) (R 1) (R 2) ←→ (g) ↓ ↑ (NE) (R 3)
Let G(x, y) := i≥0, j≥0

g i,j (x i /i) (y j /j!); R i (y) := j≥0 g i,j (y j /j!) (i ≥ 0); C j (x) := i≥0 g i,j (x i /i) (j ≥ 0) be the exponential generating functions for the matrix itself, its rows and columns, respectively.

Proposition 10.1. The following four properties are equivalent:

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

(10.2) ∂ 2 G(x, y) ∂x 2 -2 ∂ 2 G(x, y) ∂x ∂y + ∂ 2 G(x, y) ∂y 2 + 2 G(x, y) = 0. Proof. It suffices to write R ′′ i (y) -2 R ′ i+1 (y) + R i+2 (y) + 2 R i (y) = j≥0 (g i,j+2
-2 g i+1,j+1 + 2 g i+2,j -2 g i,j )(y j /j!), and, similarly,

C ′′ j (x) - 2 C ′ j+1 (x) + C j+2 (x) + 2 C j (x) = i≥0
(g i+2,j -2 g i+1,j+1 + 2 g i,j+2 -2 g i,j )(x i /i!) to obtain the equivalence between the first three properties.

As for the last one, simply note that G(x, y) = i≥0 R i (y) x i /i! = j≥0 C j (x) y j /j! and make the appropriate derivations.

Proposition 10.2. We have

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

Proof. Let ξ := x + y, η := y. Then, ∂G/∂x = ∂G/∂ξ; ∂G/∂y = ∂G/∂ξ + ∂G/∂η;

∂ 2 G/∂x 2 = ∂ 2 G/∂ξ 2 ; ∂ 2 G/∂y 2 = ∂ 2 G/∂ξ 2 + 2 ∂ 2 G/∂ξ ∂η + ∂ 2 G/∂η 2 ;
∂ 2 G/∂x ∂y = ∂ 2 G/∂ξ 2 + ∂ 2 G/∂ξ ∂η. Thus, (10.2) can be rewritten as

(10.4) ∂ 2 G ∂η 2 + 2 G = 0.
The ordinary differential equation G ′′ + 2 G = 0, whose characteristic polynomial is r 2 + 2 = 0, has a general solution of the form A cos( √ 2 η) + B sin( √ 2 η), so that the general solution of (10.2) is exactly given by (10.3).

The exact expression for the generating function G(x, y) can then be derived, if A(x + y) and B(x + y) can be obtained by an independent calculation, as done in the sequel. i,j := 0, if i + j ≡ p mod 2; f n (m, k), if i + j ≡ p + 1 mod 2; with k := j+1, m := i+j+2, 2n := p+(i+j)+1. The latter equation makes sense, as i+j and p are of different parity. The mapping (p, i, j) → (n, m, k) is one-to-one, the reverse mapping being: p := 2nm + 1, i := mk -1, j := k -1. Thus, for p ≥ 0, the matrix Λ (2p+1) reads:

      0 1 2 3 4 5 0 f p+1 (2, 1) 0 f p+2 (4, 3) 0 f p+3 (6, 5) 0 • • • 1 0 f p+2 (4, 2) 0 f p+3 (6, 4) 0 • • • 2 f p+2 (4, 1) 0 f p+3 (6, 3) 0 • • • 3 0 f p+3 (6, 2) 0 • • • 4 f p+3 (6, 1) 0 • • • 5 0 • • • 6 • • •       ;
and for p ≥ 1, the matrix Λ (2p) is equal to

      0 1 2 3 4 5 0 0 f p+1 (3, 2) 0 f p+2 (5, 4) 0 f p+3 (7, 6) 1 f p+1 (3, 1) 0 f p+2 (5, 3) 0 f p+3 (7, 5) • • • 2 0 f p+2 (5, 2) 0 f p+3 (7, 4) • • • 3 f p+2 (5, 1) 0 f p+3 (7, 3) • • • 4 0 f p+3 (7, 2) • • • 5 f p+3 (7, 1) • • • 6 • • •       . Proposition 10.3. Every matrix Λ (p) (p ≥ 0) is a Poupard matrix.
Proof. Using Definition (10.5) we have

λ (p) i,j+2 -2 λ (p) i+1,j+1 + λ (p) i+2,j + 2 λ (p) i,j = f n+1 (m + 2, k + 2) -2 f n+1 (m + 2, k + 1) + f n+1 (m + 2, k) + 2 f n (m, k) = ∆ k f n+1 (m + 2, k) + 2 f n (m, k) = 0,
by rule (R 4).

3. The first matrix Λ (1) . The counter-diagonal of Λ (1) at depth 2i (i ≥ 0) reads

λ (1) 2i,0 = f i+1 (2i + 2, 1); λ (1) 2i-1,1 = f i+1 (2i + 2, 2); • • • • • • λ (1) 2i-j,j = f i+1 (2i + 2, j + 1); • • • λ (1) 0,2i = f i+1 (2i + 2, 2i + 1).
Those (2i + 1) terms are equal to the first (2i + 1) entries of the (2i + 2)-nd row of the matrix M i+1 , that is, to the single term f 1 (2, 1) = 1 for i = 0 and for i ≥ 1 to

f i (1, •) = 0, f i (2, •), . . . , f i (j + 1, •), . . . , f i (2i, •), 0,
by virtue of (I 2). Thus, Λ (1) is identical to the Poupard matrix (f i (j+1, •)) (i, j ≥ 0):

          0 1 2 3 4 5 6 0 1 0 0 0 0 0 0 1 0 f 1 (2, •) 0 f 2 (4, •) 0 f 3 (6, •) 2 0 0 f 2 (3, •) 0 f 3 (5, •) 3 0 f 2 (2, •) 0 f 3 (4, •) 4 0 0 f 3 (3, •) 5 0 f 3 (2, •) 6 0           , equal to             0 1 2 3 4 5 6 • • • 0 1 0 0 0 0 0 0 • • • 1 0 1 0 1 0 4 • • • 2 0 0 2 0 8 • • • 3 0 1 0 10 • • • 4 0 0 8 • • • 5 0 4 • • • 6 0 • • • • • • •             , 4.
The first two columns of Λ (p) . In the sequel the column labeled j of Λ (p) will be denoted by Λ (p)

•,j and the exponential generating function for that column by Λ (p)

•,j (x) = i≥0 λ (p) i,j x i /i!. Also, Λ (p) (x, y) := j≥0 Λ (p)
•,j (x)y j /j! will be the double exponential generating function for the matrix Λ (p) .

Proposition 10.4. The first two columns of each matrix Λ (p) (p ≥ 2) are related to the columns of Λ (1) by the identities:

(10.6) Λ (p) •,0 (x) = Λ (1)
•,p-1 (x), Λ

•,1 (x) = d dx Λ

(1)

•,p-1 (x) + Λ (1) •,p (x). Proof. For the first identity it suffices to prove λ

(p) i,0 = λ (1) i,p-1 , that is f n (i + 2, 1) = f n (p + i + 1, p)
when 2n = p + i + 1. This is true by Theorem 1.2. For the second identity it suffices to prove λ

(p) i,1 = λ (1) i+1,p-1 + λ (1) i,p , that is (10.7) f n (i + 3, 2) = f n (p + i + 2, p) + f n (p + i + 2, p + 1) when 2n = p + i + 2. But by (I 4) f n (i + 3, 2) = f n (i + 2, 1) + f n (i + 3, 1),
so that by Theorem 1.2, identity (10.7) holds.

5. Solving the partial differential equation. By (10.6)

Λ (p) (x, y) {y=0} = Λ (p) •,0 (x) = Λ (1) •,p-1 (x); ∂ ∂y Λ (p) (x, y) {y=0} = Λ (p) •,1 (x) = d dx Λ (1)
•,p-1 (x) + Λ (1)

= A(x) = Λ (1)
•,p-1 (x); ∂Λ (p) (x, y) ∂y

{y=0} = A ′ (x) + √ 2 B(x) = d dx Λ (1)
•,p-1 (x) + Λ (1) •,p (x).

Consequently, A(x) = Λ

(1)

•,p-1 (x) and B(x) = Λ

(1)

•,p (x)/ √ 2 and the general expression for Λ p (x, y) reads:

(10.8) Λ (p) (x, y) = Λ (1) •,p-1 (x + y) cos( √ 2 y) + Λ (1) •,p (x + y) sin( √ 2 y)/ √ 2.
This expression still holds for p = 1. We know that Λ

(1)

•,0 (x) = 1. On the other hand, the coefficient of

x 2k+1 /(2k + 1)! (k ≥ 0) in Λ (1) •,1 (x) is f k+1 (2, •) = T 2k+1 /2 k . Hence, Λ (1) •,1 (x) = √ 2 tan(x/ √ 2) and Λ (1) (x, y) = cos( √ 2 y) + √ 2 tan x + y √ 2 sin( √ 2 y) √ 2 = cos x -y √ 2 cos x + y √ 2 , ( 10
.9) a result already obtained by Poupard.

Remark. For getting the solution for Λ (1) (x, y) we can also start with the general expression displayed in (10.3) and calculate A and B with the initial conditions Λ (1) (0, y) = Λ (1) (x, 0) = 1. We find

Λ (1) (x, y) = cos( √ 2y) + 1 -cos( √ 2(x + y)) sin( √ 2(x + y)) sin( √ 2y) = sin( √ 2x) + sin( √ 2y) sin( √ 2(x + y)) , (10.10)
an expression which is naturally equal to the right-hand side of (10.9) (by a simple trigonometric calculation).

We have not worked out other explicit formulas for Λ (p) (x, y) when p ≥ 3, but only derived the exponential generating function for those series, as explained in the next subsection. 6. A generating function for the lower triangles. By (10.9)

∂ ∂y Λ (1) (x, y) = ∂ ∂y cos x -y √ 2 cos x + y √ 2 = sin( √ 2x) √ 2 cos 2 x + y √ 2 . (10.11) Let Λ(x, y, z) := p≥1 Λ (p) (x, y) z p-1 (p -1)! . Then, Λ(x, y, z) = cos( √ 2 y) p≥1 z p-1 (p -1)! Λ (1)
•,p-1 (x + y)

+ sin( √ 2 y) √ 2 p≥1 z p-1 (p -1)! Λ (1) •,p (x + y) [by (10.8)] = cos( √ 2 y) Λ (1) (x + y, z) + sin( √ 2 y) √ 2 ∂ ∂z Λ (1) (x + y, z), since Λ (1) (x, z) = p≥0 z p p! Λ (1) •,p (x)
.

By (10.11) we then get:

Λ(x, y, z) = cos( √ 2 y) cos x + y -z √ 2 cos x + y + z √ 2 + sin( √ 2 y) sin( √ 2(x + y)) 2 cos 2 x + y + z √ 2 = cos( √ 2 x) + cos( √ 2 y) cos( √ 2 z) 2 cos 2 x + y + z √ 2 . Now, express Λ(x, y, z) as a series in the f n (m, k)'s. By definition, Λ(x, y, z) = p,i,j λ (p) i,j z p-1 (p -1)! x i i! y j j! (p ≥ 1, i ≥ 0, j ≥ 0); so that by (10.5) Λ(x, y, z) = k,m,n f n (m, k) x m-k-1 (m -k -1)! y k-1 (k -1)! z 2n-m (2n -m)! ,
the latter sum over the set {2 ≤ k + 1 ≤ m ≤ 2n}. This achieves the proof of Theorem 1.4.

Note that the right-hand side of (1.12) is symmetric in y, z, that is, Λ(x, y, z) = Λ(x, z, y). The change y ↔ z in the left-hand side of (1.12) shows that

f n (2n + 1 -k, 2n + 1 -m) = f n (m, k),
the symmetry proved for the entries f n (m, k) such that m ≥ k + 1.

Remark. Let z = 0 in (1.14). We get

2≤k+1≤2n f n (2n, k) x 2n-k-1 (2n -k -1)! y k-1 (k -1)! = cos( √ 2 x) + cos( √ 2 y) 2 cos 2 x + y √ 2 ; or, i≥0, j≥0 λ
(1) i,j

x i i! y j j! = Λ (1) (x, y) = cos( √ 2 x) + cos( √ 2 y) 2 cos 2 x + y √ 2 ; which is another expression for Λ (1) (x, y) than (10.9) and (10.10).

7.

A generating function for the upper triangles. The entries f n (m, k) (1 ≤ m < k ≤ 2n) from the upper triangles in the matrices M n (n ≥ 1) are next recorded as entries ω (p) i,j (p ≥ 0, i ≥ 0, j ≥ 0) of infinite matrices Ω (p) = (ω (p) i,j ) (i ≥ 0, j ≥ 0) as follows. Define ω (p) i,j := 0, if i + j ≡ p mod 2; f n (m, k), if i + j ≡ p mod 2; with m := p + 1, k := p + j + 2, 2n := p + i + j + 2. Conversely, i := 2nk, j := km -1, p := m -1. Thus, for p ≥ 0

Ω (2p+1) =       0 1 2 3 0 0 f p+2 (2p + 2, 2p + 4) 0 • • • 1 f p+2 (2p + 2, 2p + 3) 0 f p+4 (2p + 2, 2p + 5) • • • 2 0 f p+3 (2p + 2, 2p + 4) • • • 3 f p+3 (2p + 2, 2p + 3) • • • 4 • • •       Ω (2p) =       0 1 2 3 0 f p+1 (2p + 1, 2p + 2) 0 f p+2 (2p + 1, 2p + 4) 0 1 0 f p+2 (2p + 1, 2p + 3) 0 • • • 2 f p+2 (2p + 1, 2p + 2) 0 • • • 3 0 • • • 4 • • •      
Remark. The first rows of all matrices M n are null, so that Ω (0) is the infinite matrix with all entries equal to zero! Also, write Ω The row labeled i of Ω (p) will be denoted by Ω i,j y j /j!. Also, Ω (p) (x, y) := i≥0 Ω (p) i,• (y)x i /i! will be the double exponential generating function for the matrix Ω (p) . As x and y play a symmetric role in (10.2), the solution in (10.2) may also be written G(x, y) = A(x + y) cos( √ 2 x) + B(x + y) sin( √ 2 x), so that the generating function of each matrix Ω (p) is of the form Ω (p) (x, y) = A(x + y) cos( √ 2 x) + B(x + y) sin( √ 2 x).

As the first row of each matrix Ω (p) is the zero sequence, we have Ω (p) (0, y) = A(y) = 0. Hence, Ω (p) (x, y) = B(x + y) sin( √ The evaluation of Ω (1) 1,• (y) is easy, as the row labeled 1 of Ω (1) is (1, 0, 1, 0, 4, 0, 34, 0, . . . ), compared with (0, 1, 0, 1, 0, 4, 0, 34, 0, . . . ), which is the sequence of the coefficients of the Taylor expansion of √ 2 tan(y/ √ 2). In fact we have ω The right-hand side of (1.13) is symmetric in x, z, that is, Ω(x, y, z) = Ω(z, y, x). The change x ↔ z in the left-hand side of (1.13) shows that f n (2n + 1k, 2n + 1m) = f n (m, k), the symmetry proved for the entries f n (m, k) such that m + 1 ≤ k.

Recently, there has been a revival of studies on arithmetical and combinatorial properties of both tangent and secant numbers. Désiré André's classical model of alternating permutations has been largely used ( [START_REF] Kuznetsov | Increasing trees and alternating permutations[END_REF][START_REF] Stanley | A Survey of Alternating Permutations[END_REF]), in particular by taking the Entringer recurrence (see [START_REF] Entringer | A combinatorial interpretation of the Euler and Bernoulli numbers[END_REF][START_REF] Poupard | De nouvelles significations énumératives des nombres d'Entringer[END_REF][START_REF] Poupard | Two other interpretations of the Entringer numbers[END_REF][START_REF] Gelineau | Bijections for Entringer families[END_REF]) into account, also by looking at their quadrant marked mesh patterns [START_REF] Kitaev | Quadrant Marked Mesh Patterns in Alternating Permutations[END_REF]. As developed in the present paper, the model of ordered binary tree, with its natural statistics "eoc" and "pom," gives rise to other refinements of those trigonometric numbers, as was also done in [START_REF] Foata | Secant Tree Calculus, 24 p[END_REF].

  . The partial difference operators ∆ m , ∆ k , act as follows on the entries of the matrices M n :∆ m f n (m, k) := f n (m + 1, k)f n (m, k); (1.6) ∆ k f n (m, k) := f n (m, k + 1)f n (m, k).

Fig. 2

 2 Fig. 2.1: Definition of the Delta Sequence.

Fig. 2. 3 :

 3 Fig. 2.3: Definition of the Gamma Sequence.

  because the two subtrees in B 2 = C 2 are incident to the same node, while in A 1 they are incident to two different nodes. Finally, C 3 = D 1 as explained in (4.1). Making all the proper cancellations in the sum ∆ m 2 T 2n+1,m,k = A -B -C + D we get identity (4.2).

k

  4)Proof. When (m, k) belongs to L(2) n , the second term in (5.1) is in bijection with 2[ , that is, the set of trees in which the end m -2 of the minimal chain is outside (resp. inside) the subtree of root k. The sum of those two terms is then 2 T 2n-1,m-2,k .When (m, k) belongs to U

Fig. 9. 1

 1 Fig. 9.1 Other definitions of the Delta sequence.

  2. A sequence of Poupard matrices for the lower triangles. The entriesf n (m, k) (1 ≤ k < m ≤ 2n) from the lower triangles in the matrices M n (n ≥ 1) are now recorded as entries λ(p) i,j (p ≥ 0, i ≥ 0, j ≥ 0) of infinite matrices Λ (p) = (λ (p) i,j ) (i ≥ 0, j ≥ 0) as follows. Define (10.5) λ (p)

  x) and∂ ∂x Ω (p) (x, y) = ∂ ∂x B(x + y) sin( √ 2x) + √ 2 B(x + y) cos(

2 x + y + z √ 2 .

 2 = f j+2 (2, 2j + 3) = f j+1 (2j + 2, •) = T 2j+1 /2 j . Thus, Ω Proposition 10.6. For all p ≥ 1 we have:As all the entries ω (p) 0,j (p ≥ 1, j ≥ 0) are null, Ω(x, y, z) = 1, i ≥ 1, j ≥ 0); so that by definition of the ω (p) i,j 's Ω(x, y, z) = k,m,n f n (m, k) x 2n-k (2nk)! y k-m-1 (km -1)! z m-1 (m -1)! , (10.16) the latter sum over the set {2 ≤ m + 1 ≤ k ≤ 2n -1}. This achieves the proof of Theorem 1.4.

Table 1 .

 1 1. Poupard's triangle. appears in Sloane's On-Line Encyclopedia of Integer Sequences [Sl06] under reference A008301 and is called Poupard's triangle. As shown by Christiane Poupard

  be the Taylor expansion of tan u, the coefficients T 2n+1 (n ≥ 0) being called the tangent numbers (see, e.g.,[START_REF] Nielsen | Traité élémentaire des nombres de Bernoulli[END_REF] p. 177-178], [Co74, p. 258-259]); Poupard further shows that each row sum f n

	u 5 5!	16 +	u 7 7!	272 +	u 9 9!	7936 + • • •


Dominique Foata

Guo-Niu Han

Finite Difference Calculus for Alternating Permutations

The finite difference equation system introduced by Christiane Poupard in the study of tangent trees is reinterpreted in the alternating permutation environment. It makes it possible to make a joint study of both tangent and secant trees and calculate the generating polynomial for alternating permutations by a new statistic, referred to as being the greater neighbor of the maximum.

Introduction

Let f = (f n (k)) (n ≥ 1, 1 ≤ k ≤ 2n -1) be a family of rational numbers, displayed in a triangular array of the form

(1.1) f = f 1 (1) f 2 (1) f 2 (2) f 2 (3) f 3 (1) f 3 (2) f 3 (3) f 3 (4) f 3 (5) f 4 (1) f 4 (2) f 4 (3) f 4 (4) f 4 (5) f 4 (6) f 4 (7) • • • • • • • • • • • • • • • • • • • • • • • • • • •
and consider the finite difference equation system

(1.2) ∆ 2 f n (k) + 4 f n-1 (k) = 0 (n ≥ 2, 1 ≤ k ≤ 2n -3),
where ∆ stands for the classical finite difference operator (see, e.g., [START_REF] Jordan | Calculus of Finite Differences. Röttig and Romwalter[END_REF])

∆f n (k) := f n (k + 1) -f n (k), (1.3) so that ∆ 2 f n (k) = f n (k + 2) -2f n (k + 1) + f n (k). (1.4)
If at each step n ≥ 2 the two entries f n (1) and f n (2) are given explicit values, the whole system (1.2) has a unique solution, as the equation ∆ 2 f n (1) + 4 f n-1 (1) = 0 yields the value of f n (3), then ∆ 2 f n (2) + 4 f n-1 (2) = 0 the value of f n (4), etc.

The same conclusion holds if the two bordered diagonals (f 1 (1), f 2 (1), f 3 (1), f 4 (1), . . . , f n (1), . . . ), (f 1 (1), f 2 (3), f 3 (5), f 4 (7), . . . , f n (2n -1), . . . ) 1 are taken as initial values. To see this we first note that the equation f 2 (1) -2f 2 (2) + f 2 (3) + 4f 1 (1) = 0 determines f 2 (2) uniquely. Assuming that the triangle (f n ′ (m)) (1 ≤ m ≤ 2n ′ -1, n ′ ≤ n) has been determined, the system ∆ 2 f n+1 (m)+4 f n (m) = 0 (1 ≤ m ≤ 2n-1) consists of (2n-1) linear equations with (2n -1) unknowns, namely, f n+1 (2), f n+1 (3), . . . , f n+1 (2n), the underlying matrix being trigonal of the form

F n+1 :=         -2 1 0 0 • • • 0 0 0 1 -2 1 0 • • • 0 0 0 0 1 -2 1 • • • 0 0 0 . . . . . . . . . . . . . . . . . . . . . . . . 0 0 0 0 • • • 1 -2 1 0 0 0 0 • • • 0 1 -2         .
As det F n+1 = -2n (n ≥ 1), the system has a unique solution.

The purpose of this paper is to solve (1.2) in four cases, when the sets of initial values called [tan1], [tan2], [sec1], [sec2] are the following:

[tan1] f 1 (1) = 1; f n (1) = 0 and f n (2) = 2 k f n-1 (k) for n ≥ 2;

[tan2] f 1 (1) = 1; f n (1) = f n (2n -1) = 0 for n ≥ 2;

[sec1] f 1 (1) = 1; f n (1) = k f n-1 (k) and f n (2) = 3 k f n-1 (k) for n ≥ 2;

[sec2] f 1 (1) = 1; f n (1) = f n (2n -1) = k f n-1 (k) for n ≥ 2;

It will be proved (see Theorem 1.5) that both initial values [tan1] and [tan2] (resp. [sec1] and [sec2]) in fact lead to the same solution of the system and, furthermore, that the solutions found for the f n (k)'s are nonnegative integral values. To avoid any confusion the solutions of (1.2) will be denoted by (g n (k)) (resp. (h n (k))) when using [tan1] (resp. [sec1]). The first numerical values of those solutions are displayed in Fig. 1.1.

g 1 (1) = 1 T 1 = 1 g 2 (1) = 0 g 2 (2) = 2 g 2 (3) = 0 T 3 = 2 g 3 (1) = 0 g 3 (2) = 4 g 3 (3) = 8 g 3 (4) = 4 g 3 (5) = 0 T 5 = 16 g 4 (1) = 0 g 4 (2) = 32 g 4 (3) = 64 g 4 (4) = 80 g 4 (5) = 64 g 4 (6) = 32 g 4 (7) = 0 T 7 = 272 h 1 (1) = 1 E 2 = 1 h 2 (1) = 1 h 2 (2) = 3 h 2 (3) = 1 E 4 = 5 h 3 (1) = 5 h 3 (2) = 15 h 3 (3) = 21 h 3 (4) = 15 h 3 (5) = 5 E 6 = 61 h 4 (1) = 61 h 4 (2) = 183 h 4 (3) = 285 h 4 (4) = 327 h 4 (5) = 285 h 4 (6) = 183 h 4 (7) = 61 [E 8 =1385
Fig. 1.1. The two triangles of the g n (k)'s and h n (k)'s.

To the right of each triangle have been calculated the row sums, which are equal, as stated in the next theorem, to the tangent numbers (resp. the secant numbers). Those classical numbers, denoted by T 2n+1 and E 2n , appear in the Taylor expansions of tan u and sec u:

tan u = n≥0 u 2n+1 (2n + 1)! T 2n+1 (1.5) = u 1! 1 + u 3 3! 2 + u 5 5! 16 + u 7 7! 272 + u 9 9! 7936 + • • • sec u = 1 cos u = n≥0 u 2n (2n)! E 2n (1.6) = 1 + u 2 2! 1 + u 4 4! 5 +
g n (k) = T 2n-1 (n ≥ 1); (1.7) k h n (k) = E 2n (n ≥ 1). (1.8)
As further mentioned, Theorem 1.1 will appear as a consequence of Theorem 1.4. It will also be shown that the generating functions for the coefficients g n (k) and h n (k) can be evaluated in the following forms.

Theorem 1.2. Let Z(x, y) := 1 + n≥1 1≤k≤2n+1 f n+1 (k) x 2n+1-k (2n + 1 -k)! y k-1 (k -1)! and Z tan (x, y) (resp. Z sec (x, y)) when f n (k) := g n (k) (resp. f n (k) := h n (k)). Then, Z tan (x, y) = sec(x + y) cos(x -y); (1.9) Z sec (x, y) = sec 2 (x + y) cos(x -y). (1.10)
As Z tan (y, x) = Z tan (x, y) and Z sec (y, x) = Z sec (x, y), this implies the following Corollary.

Corollary 1.3. The entries g n (k) and h n (k) have the symmetry property:

(1.11) g n (k) = g n (2n -k), h n (k) = h n (2n -k) (1 ≤ k ≤ 2n -1).
In view of (1.7) and (1.8), two finite sets A 2n-1 and A 2n , of cardinalities T 2n-1 and E 2n , are to be found, together with a statistic, call it "grn," defined on those sets with the property that σ∈A 2n-1

x grn σ = k g n (k)x k ; (1.11) σ∈A 2n x grn σ = k h n (k)x k . (1.12)
We shall use Désiré André's old result [An1879, An1881], who introduced the notion of alternating permutation, as being a permutation σ = σ(1)σ(2) • • • σ(n) of 12 • • • n with the property that σ(1) > σ(2), σ(2) < σ(3), σ(3) > σ(4), etc. in an alternating way. For each n ≥ 1 let A n denote the set of all alternating permutations of 12 • • • n. He proved that #A 2n-1 = T 2n-1 , #A 2n = E 2n . The desired statistic "grn" is then the following.

Definition. Let σ = σ(1)σ(2) • • • σ(n) be an alternating permutation from A n , so that σ(i) = n for a certain i (1 ≤ i ≤ n).
By convention, let σ(0) = σ(n + 1) := 0. Define the greater neighbor of n in σ to be grn(σ) := max{σ(i -1), σ(i + 1)}. (1.13) Also, let

A n,k := {σ ∈ A n : grn(σ) = k} (0 ≤ k ≤ n -1). (1.14)
Theorem 1.4. Under the same assumptions as in Theorem 1.1 we have

g n (k) = #A 2n-1,k-1 (n ≥ 1, 1 ≤ k ≤ 2n -1); (1.15) h n (k) = #A 2n,k (n ≥ 1, 1 ≤ k ≤ 2n -1). (1.

16)

Example. There are T 3 = 2 alternating permutations of length 3, namely, 213 and 312, and grn(213) = grn(312) = 1, so that g 2 (1) = #A 3,0 = 0, g 2 (2) = #A 3,1 = 2, g 2 (3) = #A 3,2 = 0; there are E 4 = 5 alternating permutations of length 4, namely, 4132, 4231, 3142, 3241, 2143, and grn(4132) = 1, grn(4231) = grn(3142) = grn(3241) = 2, grn(2143) = 3, so that h 2 (1) = 1, h 2 (2) = 3, h 2 (3) = 1; in accordance with the numerical values in Fig. 1.1.

As #A 2n-1 = T 2n-1 , #A 2n = E 2n , following Désiré André's result, it is now clear that Theorem 1.1 is a consequence of Theorem 1.4. Thus, an analytical result is proved by combinatorial methods.

In Proposition 2.1 it will be proved that #A

1,0 = 1, #A 2n-1,0 = #A 2n-1,2n-2 = 0 (n ≥ 2) and #A 2n-1,1 = 2 T 2n-3 (n ≥ 2); also, #A 2,1 = 1, #A 2n,1 = #A 2n,2n-1 = E 2n-2 (n ≥ 2) and #A 2n,2 = 3 E 2n-2 (n ≥ 2).
In view of Theorem 1.4 this implies that conditions [tan2] and [sec2] are fulfilled as soon as conditions [tan1] and [sec1] hold, and then the following theorem.

Theorem 1.5. The entries (g n (k)) and (h n (k)) given by (1.15) and (1.16) are also solutions of the finite difference equation system (1.2) when the initial values [tan2] and [sec2] are used, respectively.

There are other combinatorial models which are also counted by tangent and secant numbers, or in a one-to-one correspondence with alternating permutations, in particular, the labeled, binary, increasing, topological trees, also called "arbres binaires croissants complets" by Viennot [START_REF] Xavier | Séries génératrices énumératives[END_REF]chap. 3,p. 111]. The set of those trees having n labeled nodes is denoted by T n . The statistic "pom" (parent of the maximum leaf ), introduced by Poupard [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF] for her strictly ordered, binary trees can be extended to all of T n . The usual bijection (see [START_REF] Xavier | Séries génératrices énumératives[END_REF]) γ : T n → A n , called projection, has the property: pom(t) = grn(γ(t)), as proved in Theorem 5.1. We then have another combinatorial interpretation for the polynomials

k g n (k)x k and k h n (k)x k .
As such, the triangle (g n (k)) (n ≥ 1, 1 ≤ k ≤ 2n -1) does not appear in Sloane's On-Line Encyclopedia of Integer Sequences [Sl06], but the triangle (g n (k)/2 n-1 ) does under reference A008301 and is called Poupard's triangle, after her pioneering work on strictly ordered binary trees [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF]. It is banal to verify that 2 n-1 divides g n (k) when dealing with the combinatorial model T n for n odd.

In contrast to Christiane Poupard [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF], who showed that the distribution of the strictly ordered binary trees satisfied the finite difference equation system ∆ 2 f 2n+1 (k)+2 f 2n-1 (k) = 0, we have used the multiplicative factor "4" in equation (1.2) to make a unified study of the tangent and secant cases and deal with objects in one-to-one correspondence with alternating permutations. Mutatis mutandis, identities (1.15), as well as (1.11) concerning the tangent numbers, are due to her. She obtains the generating function for her trees in the form: sec((x + y)/ √ 2) cos((x -y)/ √ 2) instead of (1.9). However, the alternating permutation development in Sections 2 and 3, identity (1.10) and the combinatorial properties of the entries h n (k) are new.

The triangle of the h n (k)'s appears in Sloane's [Sl06] as sequence A125053. It was deposited there by Paul D. Hanna. The entries have been calculated by using a procedure equivalent to (1.2) and the initial condition [tan2]. No combinatorial interpretation is given and no generating function calculated.

Theorem 1.4 will be proved in Section 3, once evaluations of some cardinalities such as #A n,k will be made, as done in Section 2. The proof of Theorem 1.2 is given in Section 4, together with further identities on the g n (k) and h n (k)'s.

Some special values

The evaluations of #A 2n-1,k-1 and #A 2n,k made in the next proposition for some values of n and k will facilitate the derivation of the proof of Theorem 1.2. They also have their own combinatorial interests.

Proposition 2.1. The following relations hold:

#A 1,0 = 1, #A 2n-1,0 = #A 2n-1,2n-2 = 0 (n ≥ 2) (2.1) #A 2n-1,1 = #A 2n-1,2n-3 = 2 T 2n-3 (n ≥ 2); (2.2) #A 2n-1,2 = #A 2n-1,2n-4 = 4 T 2n-3 (n ≥ 3); (2.3) #A 2n-1,3 = #A 2n-1,2n-5 = 6 T 2n-3 -8 T 2n-5 (n ≥ 3); (2.4) k≥0 #A 2n-1,k = T 2n-1 (n ≥ 1). (2.5) #A 2,1 = 1; (2.6) #A 2n,1 = #A 2n,2n-1 = E 2n-2 (n ≥ 2); (2.7) #A 2n,2 = #A 2n,2n-2 = 3 E 2n-2 (n ≥ 2); (2.8) #A 2n,3 = #A 2n,2n-3 = 5 E 2n-2 -4 E 2n-4 (n ≥ 2); (2.9) k≥1 #A 2n,k = E 2n (n ≥ 1). (2.10) Proof.
(2.1) The set A 1 is the singleton 1 and grn(1) = 0 by definition, so that #A 1,0 = 1. For n ≥ 2 all alternating permutations from A 2n-1 have a "grn" at least equal to 1. Hence, #A 2n-1,0 = 0. Finally, each alternating permutation of length (2n -1) (n ≥ 2) contains neither the factor (2n -2)(2n -1), nor (2n -1)(2n -2). Hence, #A 2n-1,2n-2 = 0.

(2.2) When n ≥ 2, each alternating permutation from A 2n-1,1 starts with (2n -1) 1, or ends with 1 (2n -1). After removal of those two letters, there remains an alternating permutation on {2, 3, . . . , 2n -2}. Hence, #A 2n-1,1 = 2 T 2n-3 . Next, each permutation from A 2n-1,2n-3 must contain, either the three-letter factor (2n -1)(2n -3)(2n -2), or (2n -2)(2n -3)(2n -1). The removal of the factor (2n -1)(2n -3) (resp. (2n -3)(2n -1)) yields an alternating permutation of the set {1, 2, . . . , (2n -4), (2n -2)}, of cardinality (2n -3). This proves relation #A 2n-1,2n-3 = 2 T 2n-3 .

(2.3) Start with an alternating permutation on {1, 3, 4, . . . , 2n -2}, then having (2n -3) elements. There are four possibilities to generate a permutation from A 2n-1,2 : (1) insert (2n -1) 2 to the left; (2) insert 2 (2n-1) to the right; (3) insert 2(2n-1) just before 1; (4) insert (2n-1) 2 just after 1. For the second identity in (2.3) proceed in the same way: in each alternating permutation on {1, 2, . . . , 2n -1} \ {2n -4, 2n -1} the two letters (2n -3), (2n -2) are necessarily local maxima. There are four possibilities to obtain a permutation from A 2n-1,2n-4 : insert (2n -1) (2n -4) just before, either (2n -3), or (2n -2); also insert (2n -4) (2n -1) just after, either (2n -3), or (2n -2).

(2.4) Each permutation from A 2n-1,3 containing the factor 2 1 (resp. 1 2) starts with 2 1 (resp. ends with 1 2). Dropping the factor 2 1 (resp. 1 2) and subtracting 2 from the remaining letters yields an alternating permutation from A 2n-3,1 . There are then 2(2 T 2n-5 ) permutations from A 2n-1,3 containing, either 2 1, or 1 2.

If a permutation from A 2n-1,3 contains neither one of those two factors, it has one of the six properties: it starts with (2n -1) 3, or contains one of the three-letter factor 1 (2n -1) 3, 3 (2n -1) 1, 2 (2n -1) 3, 3 (2n -1) 2, or still ends with 3 (2n -1). After removal of the two-letter factor (2n -1) 3 or 3 (2n -1) there remains an alternating permutation on {1, 2, 4, . . . , (2n -2)} not starting with 2 1 and not ending with 1 2. There are then 6(T 2n-3 -2 T 2n-5 ) such permutations. Altogether, #A 2n-1,3 = 4 T 2n-5 + 6(T 2n-3 -2 T 2n-5 ) = 6 T 2n-3 -8 T 2n-5 .

The proof of the second identity in (2.4) follows a different pattern. If the letter (2n -4) is a local minimum (i.e., less than its two adjacent letters) in a permutation σ from A 2n-1,2n-5 , then σ necessarily contains one of the four five-letter factors (2n -1)(2n -5)(2n -2)(2n -4)(2n -3), (2n -1)(2n -5)(2n -3)(2n -4)(2n -2), (2n -2)(2n -4)(2n -3)(2n -5)(2n -1), (2n -3)(2n -4)(2n -2)(2n -5)(2n -1). Replacing this fiveletter factor by (2n -5) yields a permutation from A 2n-5 . Thus, there are 4 T 2n-5 permutations from A 2n-1,2n-5 in which (2n -4) is a local minimum.

In the other permutations from A 2n-1,2n-5 all the four letters (2n -4), (2n -3), (2n -2), (2n -1) are local maxima (i.e., greater than their adjacent letters). Let A ′ 2n-1,2n-5 be the set of those permutations. When the two-letter factor (2n -1)(2n -5) or (2n -5)(2n -1) is deleted from such a permutation, there remains a permutation on {1, 2, . . . , (2n -1)} \ {(2n -5), (2n -1)} in which the third largest letter (2n -4) is not a local minimum. Let A ′′ 2n-3 be the set of those permutations. But the alternating permutations on the latter set in which (2n -4) is a local minimum necessarily contain the three-letter factor (2n -3)(2n -4)(2n -2) or (2n-2)(2n-4)(2n-3). There are then 2 T 2n-5 such permutations. Hence, #A ′′ 2n-3 = T 2n-3 -2 T 2n-5 . To obtain a permutation from A ′ 2n-1,2n-5 it suffices to start from a permutation σ ′′ from A ′′ 2n-3 and insert (2n-1)(2n-5) (resp. (2n-5)(2n-1)) just before (resp. just after) each one of the three letters (2n -4), (2n -3), (2n -2) (which are all local maxima). There are then 6(T 2n-3 -2 T 2n-5 ) such permutations. Altogether, #A 2n-1,2n-5 = 4 T 2n-5 + 6(T 2n-3 -2 T 2n-5 ) = 6 T 2n-3 -8 T 2n-5 . No comment for (2.5) and (2.6).

(2.7) Simply note that the only alternating permutations from A 2n,1 and A 2n,2n-1 are, respectively, of the form:

(2n) 1 σ(3) • • • σ(2n) and σ(1)σ(2) • • • (2n) (2n -1).
(2.8) Same proof as for (2.3): start with an alternating permutation on {1, 3, 4, . . . , (2n-1)}. There are exactly three possibilities to generate a permutation from A 2n,2 : insert (2n) 2 to the left, or just after the letter 1, or still insert 2 (2n) just before the letter 1. For the second identity start with a permutation on {1, 2, . . . , 2n} \ {2n -2, 2n} and insert (2n) (2n -2) either to the right, or just before (2n -1), or still insert (2n -2) (2n) just after (2n -1).

(2.9) Each permutation from A 2n,3 containing the factor 2 1 is necessarily of the form σ = 2 1 σ(3) • • • σ(2n), so that the alternating permutation σ ′ := (σ(3) -2) • • • (σ(2n) -2) belongs to A 2n-2,1 . There are then E 2n-4 such permutations. If a permutation from A 2n,3 does not contain 2 1, it has one of the five properties: it starts with (2n) 3, or contains one of the three-letter factor 1 (2n) 3, 3 (2n) 1, 2 (2n) 3, 3 (2n) 2. After removal of the two-letter factor (2n) 3 or 3 (2n) there remains an alternating permutation on {1, 2, 4, . . . , (2n -1)} not starting with 2 1. There are then 5(E 2n-2 -E 2n-4 ) such permutations. Altogether,

#A 2n,3 = E 2n-4 + 5(E 2n-2 -E 2n-4 ) = 5E 2n-2 -4E 2n-4 .
The proof for the second identity in (2.9) is quite similar. Each permutation from A 2n,2n-3 containing the factor (2n-1)(2n-2) necessarily ends with the four-letter factor (2n)(2n -3)(2n -1)(2n -2). There are then E 2n-4 such permutations. The other permutations from A 2n,2n-3 contain one of the four three-letter factors (2n)(2n-3)(2n-2), (2n-2)(2n-3)(2n), (2n)(2n -3)(2n -1), (2n -1)(2n -3)(2n), or ends with (2n)(2n -3). After removal of the two-letter factor (2n)(2n -3) or (2n -3)(2n) there remains an alternating permutation on {1, 2, . . . , (2n -4), (2n -2), (2n -1)}, not ending with the two-letter factor (2n-1)(2n-2). There are E 2n-2 -E 2n-4 such permutations. Altogether, #A 2n,2n-3 = E 2n-4 + 5(E 2n-2 -E 2n-4 ).

No comment for (2.10).

Proof of Theorem 1.4

Let a n (k) := #A 2n-1,k-1 and b n (k) := #A 2n,k . From Proposition 2.1 it follows that the initial conditions [tan1] and [tan2] hold when f n (k) = a n (k), and [sec1] and also [sec2] when f n (k) = b n (k). It remains to prove that in each case (1.2) holds.

By means of identities (2.2)-(2.4) and (2.7)-(2.9) we easily verify that (1.2) holds for both a n (k) and b n (k) when n = 2, 3 and 1 ≤ k ≤ 2n -3. It also holds for a n (k) when n ≥ 4 and k = 1, 2, 2n -4, 2n -3, and for b n (k) when n ≥ 4 and k = 1, 2n -3.

What is left to prove is: ∆ 2 a n (k)+4a n-1 (k) = 0, that is, ∆ 2 A 2n-1,k-1 + 4 A 2n-3,k-1 = 0 for n ≥ 4 and 3 ≤ k ≤ 2n -5-by identifying each finite set with its cardinality-and also ∆ Using those notations we get

2 b n (k) + 4b n-1 (k) = 0, that is, ∆ 2 A 2n,k + 4 A 2n-2,k = 0 for n ≥ 4 and 2 ≤ k ≤ 2n -4; altogether, (2.11) ∆ 2 A n,k + 4 A n-2,k = 0 for n ≥ 7 and 2 ≤ k ≤ n -4 (n even) 2 ≤ k ≤ n -5 (n odd). Let v = y 1 • • • y m be
A n,k = 0≤y≤k-1 [ynk] = 0≤y≤k-1 [ynk(k + 1)] + 0≤y≤k-1 k+2≤z≤n-1 [ynkz] + 1≤y≤k-1 [ynk0]; A n,k+1 = 0≤y≤k [yn(k + 1)] = [kn(k + 1)] + 0≤y≤k-1 k+2≤z≤n-1 [yn(k + 1)z] + 1≤y≤k-1 [yn(k + 1)0].
The transposition (k, k + 1) maps the set [ynkz] onto the set [yn(k + 1)z] for z ∈ {k + 2, . . . , n -1} ∪ {0}, so that we may write

∆ A n,k = A n,k+1 -A n,k = [kn(k + 1)] - 0≤y≤k-1 [ynk(k + 1)] = [kn(k + 1)] - 0≤y 1 ,y 2 ≤k-1 y 1 =y 2 [y 1 nk(k + 1)y 2 ]; ∆ A n,k+1 = A n,k+2 -A n,k+1 = [(k + 1)n(k + 2)] - 0≤y≤k [yn(k + 1)(k + 2)] = [(k + 1)n(k + 2)] -[kn(k + 1)(k + 2)] - 0≤y≤k-1 [yn(k + 1)(k + 2)k] - 0≤y 1 ,y 2 ≤k-1 y 1 =y 2 [y 1 n(k + 1)(k + 2)y 2 ]. For 2 ≤ k ≤ n -4 the permutation k k+1 k+2 k+1 k+2 k maps [y 1 nk(k + 1)y 2 ] onto [y 1 n(k + 1)(k + 2)y 2 ] in a bijective manner. Hence, ∆ 2 A n,k = ∆ A n,k+1 -∆ A n,k = [(k + 1)n(k + 2)] -[kn(k + 1)(k + 2)] - 0≤y≤k-1 [yn(k + 1)(k + 2)k] -[kn(k + 1)]. But [kn(k + 1)] = [(k + 2)kn(k + 1)] + [kn(k + 1)(k + 2)] + z 1 ,z 2 ∈{k+3,...,n-1}∪{0} z 1 =z 2 [z 1 kn(k + 1)z 2 ].
Again, the permutation k k+1 k+2 k+1 k+2 k maps the last sum onto the set

[(k + 1)n(k + 2)]. Altogether, as [(k + 2)kn(k + 1)] = [kn(k + 1)(k + 2)], we have ∆ 2 A n,k = -3 [kn(k + 1)(k + 2)] - 0≤y≤k-1 [yn(k + 1)(k + 2)k].
When removing the factor (k + 1)(k + 2) and replacing each integer z ≥ k+2 by (z-2), in each alternating permutation, both sets [kn(k+1)(k+2)] and 0≤y≤k-1

[yn(k + 1)(k + 2)k] are transformed into A n-2,k ; so that ∆ 2 A n,k = -4 A n-2,k .

The bivariate generating functions

Let f = (f n (k)) (n ≥ 1, 1 ≤ k ≤ 2n -1) be the family of rational numbers, as displayed in (1.1), that satisfies the finite-difference equation system (1.2) under the initial conditions [tan2] of [sec2]. We know that the system has then a unique solution. With the triangle f associate the infinite matrix

(4.1) Γ = (γ ij ) (i≥0,j≥0) :=          f 1 (1) 0 f 2 (3) 0 f 3 (5) 0 f 4 (7) • • • 0 f 2 (2) 0 f 3 (4) 0 f 4 (6) • • • f 2 (1) 0 f 3 (3) 0 f 4 (5) • • • 0 f 3 (2) 0 f 4 (4) • • • f 3 (1) 0 f 4 (3) • • • 0 f 4 (2) • • • f 4 (1) • • •          .
In other words, define γ ij := 0 when i + j is odd, and γ ij := f n (k) with k := j + 1, 2n = 2 + i + j when i + j is even. For i + j even the mapping (i, j) → (n, k) is one-to-one, the reverse mapping being for

n ≥ 1, 1 ≤ k ≤ 2n -1 given by i = 2n -1 -k, j = k -1.
In terms of the entries γ ij relation (1.2) may be written in the form

γ i,j = 2 γ i-1,j-1 + 1 2 (γ i-1,j+1 + γ i+1,j-1 ) (i ≥ 1, j ≥ 1); (4.2) γ ij = 0, if i + j odd. (4.3)
Furthermore, the full matrix Γ = (γ i,j ) (i ≥ 0, j ≥ 0) is completely determined as soon as its first row (γ 0,j ) (j ≥ 0) and first column (γ i,0 ) (i ≥ 0) are known. Let f → Γ denote the above correspondence between those triangles and matrices.

Let Z(x, y) := i≥0, j≥0 γ i,j

x i i! y j j! . It is easily verified that Z(x, y) satisfies the partial differential equation

(4.4) ∂ 2 Z(x, y) ∂x ∂y = 2 Z(x, y) + 1 2 ∂ 2 Z(x, y) ∂x 2 + 1 2 ∂ 2 Z(x, y) ∂y 2 ,
if and only if the coefficients γ i,j satisfy relation (4.2). Hence, Z(x, y) is fully determined by (4.4) and by the generating functions Z(x, 0) = i≥0 γ i,0 x i /i! and Z(0, y) = j≥0 γ 0,j y j /j! for the first column and first row of the matrix Γ. But for any given formal power series in one variable f

(x) = 1 + n≥1 f 2n x 2n (2n)
! it can be also verified that the bivariate formal power series

(4.5) Z(x, y) = i≥0, j≥0 γ i,j x i i! y j j! = f (x + y) sec(x + y) cos(x -y)
satisfies (4.4) and that the generating functions for its first column and first row are given by f (x) and f (y), respectively. This proves the following proposition.

Proposition 4.1. Let f (x) = 1 + n≥1 f 2n x 2n (2n)
! be given and Γ = (γ ij ) (i ≥ 0, j ≥ 0) be an infinite matrix, whose entries satisfy relations (4.2) and (4.3), on the one hand, and such that γ 0,0 = 1, γ 2n+1,0 = γ 0,2n+1 = 0 for n ≥ 0 and γ 2n,0 = γ 0,2n = f 2n for n ≥ 1, on the other hand. Then, identity (4.5) holds.

Using the correspondence γ ij ↔ f n (k) above mentioned, the series Z(x, y) can be rewritten

(4.6) Z(x, y) = 1 + n≥1 1≤k≤2n+1 f n+1 (k) x 2n+1-k (2n + 1 -k)! y k-1 (k -1)! ,
which is then equal to f (x + y) sec(x + y) cos(x -y) under the assumptions of the previous proposition. Now, consider the two triangles described in Fig. 1.1 and let Γ tan = (γ tan ij ) and Γ sec = (γ sec ij ) be the two Γ-matrices attached to them:

Γ tan = (γ tan ij ) =          g 1 (1) 0 g 2 (3) 0 g 3 (5) 0 g 4 (7) • • • 0 g 2 (2) 0 g 3 (4) 0 g 4 (6) • • • g 2 (1) 0 g 3 (3) 0 g 4 (5) • • • 0 g 3 (2) 0 g 4 (4) • • • g 3 (1) 0 g 4 (3) • • • 0 g 4 (2) • • • g 4 (1) • • •          ; Γ sec = (γ sec ij ) =          h 1 (1) 0 h 2 (3) 0 h 3 (5) 0 h 4 (7) • • • 0 h 2 (2) 0 h 3 (4) 0 h 4 (6) • • • h 2 (1) 0 h 3 (3) 0 h 4 (5) • • • 0 h 3 (2) 0 h 4 (4) • • • h 3 (1) 0 h 4 (3) • • • 0 h 4 (2) • • • h 4 (1) • • •          .
The exponential generating function for the first row and first column of Γ tan is equal to f (x) = 1. On the other hand, as h n (1) = h n (2n + 1) = #A 2n,1 = E 2n-2 by [sec2], (1.8) and (1.16), the exponential generating function for the first row and first column of Γ sec is equal to h 1 (1)+h 2 (1)x 2 /2!+h 3 (1)

x 4 /4!+• • • = E 0 +E 2 x/2!+E 4 x 4 /4+• • • = sec(x).
Theorem 1.2 is then a consequence of the previous Proposition.

When (x, y) is equal to (x, x), then to (x, -x) in (1.9) and (1.10), we obtain: Z tan (x, x) = sec(2x); Z tan (x, -x) = cos(2x); Z sec (x, x) = sec 2 (2x) = 1 + n≥1 4 n T 2n+1 x 2n /(2n)! and Z sec (x, -x) = cos(2x). Looking for the coefficients of x 2n /(2n)! on both sides in the first (resp. last) two formulas yields four further identities

1≤k≤2n+1 2n k -1 g n+1 (k) = 4 n E 2n (n ≥ 1); (4.7) 1≤k≤2n+1 (-1) k 2n k -1 g n+1 (k) = (-1) n 4 n (n ≥ 1); (4.8) 1≤k≤2n+1 2n k -1 h n+1 (k) = 4 n T 2n+1 (n ≥ 1) (4.9) 1≤k≤2n+1 (-1) k 2n k -1 h n+1 (k) = (-1) n 4 n (n ≥ 1). (4.10)
The last two ones are mentioned in Sloane's Encyclopedia [START_REF] Sloane | On-line Encyclopedia of Integer Sequences[END_REF] (sequence A125053) without proofs.

Alternating permutations and binary trees

In this Section the traditional vocabulary on trees, such as node, leaf, child, root, . . . is used. In particular, when a node is not a leaf, it is said to be an internal node.

Definition. An n-labeled, binary, increasing, topological tree is defined by the following axioms:

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

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

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

(4) the tree is planar and each child of a node is, either on the left (it is then called the left child), or on the right (the right child);

(5) when n is odd, each node is, either a leaf, or a node with two children; when n is even, each node is, either a leaf, or a node with two children, except the rightmost node (uniquely defined) which has one left child, but no right child. It will be referred to as being the one-son child.

Each such binary tree t may be drawn on a Euclidean plane: the root has coordinates (0, 0), the left son of the root (-1, 1) and the right son (1, 1), the grandsons (-3/2, 2), (-1/2, 2), (1/2, 2), (3/2, 2), respectively, the great-grandsons (-7/4, 3), (-5/4, 3), . . . , (7/4, 3), etc. With this convention all the nodes have different abscissas. Let t have n nodes and make the orthogonal projections of those nodes on a horizontal axis. Writing the labels of the projected n nodes yields a permutation σ

= σ(1)σ(2) • • • σ(n) of 1 2 • • • n.
We say that σ is the projection of t and t the spreading out of σ. Moreover, σ is alternating. For instance, the two trees t 1 and t 2 in Fig. 1.2 are labeled, binary, increasing, topological trees, with 7 and 8 nodes, respectively. Their projections σ 1 = 6 1 5 4 7 2 3 and σ 2 = 6 1 5 4 8 2 7 3 are alternating.

For each n ≥ 1 let T n be the set of all n-labeled, binary, increasing, topological trees. Then, t → σ is a bijection of T n onto A n , so that we also have: #A 2n+1 = T 2n+1 , #A 2n = E 2n . Each tree t from T n is said to be tangent (resp. secant), if n is odd (resp. even).

5 7 The two statistics "emc" ("end of minimal chain") and "pom" ("parent of maximum leaf") we now define on each set T n have been introduced by Christiane Poupard [START_REF] Poupard | Deux propriétés des arbres binaires ordonnés stricts[END_REF] in her study of the strictly ordered binary trees and provide two other combinatorial interpretations for the entries g n (k) and h n (k). Their definitions are also valid for all binary increasing trees, in particular, for secant and tangent trees. Let n ≥ 2 and t be a binary increasing tree, with n nodes labeled 1, 2, . . . , n. Let a be the label of an internal node. If the node has two children labeled b and c, define min a := min{b, c}; if it has one child b, let min a := b. The minimal chain of t is defined to be the sequence a 1 → a 2 → a 3 → • • • → a j-1 → a j , with the following properties:

4 3 6 2 1 ❅ ❅✘ ✘ ✘ ✘ ✘ ✘ ❍ ❍ ❍ ❅ ❅ 6 1 5 4 7 2 3 σ 1 = t 1 = 5 8 4 7 6 2 1 3 ❅ ❅✘ ✘ ✘ ✘ ✘ ✘ ✟ ✟ ✟ ❍ ❍ ❍ ❅ ❅ ❅ ❅ 6
(i) a 1 = 1 is the label of the root;

(ii) for i = 1, 2, . . . , j -1 the i-th term a i is the label of an internal node and a i+1 = min a i ;

(iii) a j is the label of a leaf. Define the end of the minimal chain in t to be: eoc(t) := a j . As t is increasing, there is a unique leaf with label n. If that leaf is incident to a node labeled k, define the (parent of the maximum leaf ) in t to be: pom(t) := k. By convention, eoc(t) = 1 and pom(t) = 0 for the unique t ∈ T 1 .

The minimal chain of the tree t 1 (resp. t 2 ) displayed in Fig. 1.2 is 1 → 2 → 3 (resp. 1 → 2 → 3 → 7). Then eoc(t 1 ) = 3, eoc(t 2 ) = 7. Also, pom(t 1 ) = 4 and pom(t 2 ) = 4.

Theorem 5.1. Let σ = σ(1)σ(2) • • • σ(n) be the projection of the nlabeled, binary, increasing, topological tree t. Then pom(t) = grn(σ). In other words, the parent of the maxium leaf in t is the greater neighbor of n in σ.

Proof. Let σ(i) = n with 2 ≤ i ≤ n -1. The parent of the node labeled n in t is, either the node labeled σ(i -1), or the node labeled σ(i + 1). Let σ(j) be the label of the node of the common ancester of the previous two nodes in t. Then, σ(j) ≤ min{σ(i -1), σ(i + 1)}, j = i and i -1 ≤ j ≤ i + 1. Hence, either σ(j) = σ(i -1) < σ(i + 1), or σ(j) = σ(i + 1) < σ(i -1). In the first (resp. the second) case the parent of n is σ(i + 1) (resp. σ(i -1)) and grn(σ) = max{σ(i -1), σ(i + 1)}.

In [START_REF] Han | The Poupard Statistics on Tangent and Secant Trees[END_REF] an explicit bijection of T n onto itself is constructed that maps the statistic "eoc -1" onto the statistic "pom." For each of the polynomials k g n (k)x k , k h n (k)x k , we then have three combinatorial interpretations: one on alternating permutations by the statistic "grn," and two on labeled, binary, increasing, topological trees by "pom" and "eoc."

Recently, there has been a revival of studies on arithmetical and combinatorial properties of both tangent and secant numbers. Ordering the alternating permutations according to their leftmost elements has led to the Entringer recurrence, having interesting properties ([En66, FZ71, FZ71a, Po97, GHZ10]). The geometry of those permutations has been fully exploited ( [START_REF] Kuznetsov | Increasing trees and alternating permutations[END_REF][START_REF] Stanley | A Survey of Alternating Permutations[END_REF]), in particular by looking at their quadrant marked mesh patterns in [START_REF] Kitaev | Quadrant Marked Mesh Patterns in Alternating Permutations[END_REF], or for defining and studying natural qanalogs of the tangent and secant numbers ([AG78, AF80, Fo81], [START_REF] Stanley | Enumerative Combinatorics[END_REF]). Further q-analogs were also introduced, based no longer on alternating permutations, but on the so-called doubloon model (see [START_REF] Foata | The doubloon polynomial triangle[END_REF][START_REF] Foata | Doubloons and q-secant numbers[END_REF][START_REF] Foata | Doubloons and new q-tangent numbers[END_REF]). The classical continued fraction expansions of secant and tangent have made possible the discovery of other q-analogs (see [Pr08, Pr00, Fu00, HRZ01, Jos10, SZ10]).

  a nonempty word with distinct letters from the set {0, 1, 2, . . . , n} and v = y m • • • y 1 be its mirror-image. If m = 1 and y 1 = 0, let [v] = [0] be the empty set. If m ≥ 2 and y 1 = 0 (resp. y m = 0), let [v] be the set of all alternating permutations from A n , if any, whose left factors are equal to y 2 • • • y m , or whose right factors are equal to y m • • • y 2 . When y 1 ≥ 1, let [v] be the set of all alternating permutations from A n , if any, containing, either the factor v, or the factor v. Finally, let [ v ] := [v].

  Fig. 1.2. Tangent, secant trees and alternating permutations.

Acknowledgement. The authors should like to thank the referee for his careful reading and his knowledgeable remarks.