Symmetric Dellac Configurations

Ange Bigeni Department of Mathematics HSE University Usacheva str. 6 Moscow 119048 Russia

                 ange.bigeni@gmail.com

Evgeny Feigin Department of Mathematics HSE University Usacheva str. 6 Moscow 119048 Russia and Skolkovo Institute of Science and Technology Nobelya Ulitsa 3 Moscow 121205 Russia

                   evgfeig@gmail.com

Abstract

We define symmetric Dellac configurations as the Dellac configurations that are symmetrical with respect to their centers. The even-length symmetric Dellac configurations coincide with the Fang–Fourier symplectic Dellac configurations. Symmetric Dellac configurations generate the Poincaré polynomials of (odd or even) symplectic or orthogonal versions of degenerate flag varieties. We give several combinatorial interpretations of the Randrianarivony–Zeng polynomial extension of median Euler numbers in terms of objects that we call extended Dellac configurations. We show that the extended Dellac configurations generate symmetric Dellac configurations. As a consequence, the cardinalities of odd and even symmetric Dellac configurations are respectively given by two sequences (1, 1, 3, 21, 267, …) and (1, 2, 10, 98, 1594, …), defined as specializations of polynomial extensions of median Euler numbers.

1 Notation and vocabulary

For a pair of integers n < m, we denote the set {n, n + 1, …, m} by [n, m]. We denote the set [1, n] by [n].

In this paper, we call tableau (plural tableaux) a rectangular grid made up of a finite number of columns and rows. We call box the intersection of a column and a row. If a tableau T has n columns and m rows, then for all j ∈ [n] and for all i ∈ [m], the j-th column of T (from left to right) is denoted by C_{j}^{T}, and the i-th row of T (from bottom to top) is denoted by L_{i}^{T}. The box C_{j}^{T} ∩ L_{i}^{T} is denoted by (j : i). In the tableaux that we study, a box may be empty or contain a point •. If the box (j : i) contains a point referred to by a letter such as p, we also write p = (j : i). If it is known that a row L_{i}^{T} contains a single point, then this point is denoted by p_{i}^{T}.

2 Introduction

Let N be a positive integer. Recall that a Dellac configuration [9] D ∈ DC_{N} is a tableau made up of N columns and 2N rows, which contains 2N points one per row, two per column. In addition, all the points are located between the lines y = x and y = N +x; in other words, if a box ( j : i ) of T contains a point, then j ≤ i ≤ N + j. The cardinality of DC_{N} is h_{N} where (h_{N})_{N≥0} = (1, 1, 2, 7, 38, 295, …) is the sequence \underline{A000366} of normalized median Genocchi numbers [1, 3, 4, 5, 14, 15, 18, 19, 20]. For D ∈ DC_{N}, let inv(D) be the number of pairs (p_{1}, p_{2}) of points of D such that p_{1} is located to the left of p_{2} and above p_{2} (such a pair is named an inversion of D). For example, we depict in Figure 1 the elements of (DC_{N})_{N∈[3]} (from top to bottom), whose inversions are represented by segments connecting the points involved.

Given an N-dimensional vector space E, a basis (e_{1}, e_{2}, …, e_{N}) of E and an integer k ∈ [N], let pr_{k} : E → E be the projection along e_{k} to the linear span of the rest basis vectors. Feigin [14] defined the degenerate flag variety F_{N}^{a} as the set of collections (V_{1}, V_{2}, …, V_{N−1}) of subspaces of E such that dim(V_{k}) = k and pr_{k+1}(V_{k}) ⊂ V_{k+1} for all k ∈ [N −1]. Feigin [14, 16, 17] proved that the Poincaré polynomial F_{N} of the degenerate flag variety F_{N}^{a} has the following combinatorial interpretation for all N ≥ 1:

F_{N}(q) = ∑_{D∈DC_{N}} q^{inv(D)}.

Figure 1: The elements of DC_{1}, DC_{2}, DC_{3} from top to bottom; the elements of SDC_{1}, SDC_{2}, SDC_{3} are framed in red.

For example, we can compute the Poincaré polynomials of (F_{N}^{a})_{N∈[3]} from Figure 1:

F_{1}(q) = 1,
F_{2}(q) = q + 1,
F_{3}(q) = q^{3} + 3q^{2} + 2q + 1.

2.1 Symmetric Dellac configurations

For a positive integer n, consider a 2n-dimensional vector space E, a basis (e_{1}, e_{2}, …, e_{2n}) of E, and a non-degenerate skew-symmetric form defined on E^{2} by (e_{i}, e_{2n+1−i}) = 1 for all i ∈ [n] and (e_{i}, e_{j}) = 0 if i + j ≠ 2n. Feigin et al. [17] defined the symplectic degenerate flag variety SpF_{2n}^{a}, as the subvariety of F_{2n}^{a} consisting of collections (V_{1}, …, V_{2n−1}) such that V_{k} = V_{2n−k}^{⊥} for all k ∈ [2n − 1]. Fang and Fourier [13] considered the action of an algebraic torus on F_{2n}^{a} [8, 7]. They parametrized the torus fixed points of SpF_{2n}^{a} ⊂ F_{2n}^{a} (the points fixed by the action of the torus) using even symmetric Dellac configurations D ∈ SDC_{2n}, which they introduced in their paper as symplectic Dellac configurations.

In a separate paper [6], we extended the definition of the symplectic degenerate flag varieties to SpF_{N}^{a} for all N ≥ 1. We proved that the Poincaré polynomials S_{N} of these varieties have the following combinatorial interpretation:

S_{N}(q) = ∑_{D∈SDC_{N}} q^{ĩnv(D)}.

Here ĩnv(D) is the number of inversions of D, modulo the rotation r_{π}. More precisely, we identify two inversions of D if they are of the form (p_{1}, p_{2}) and (r_{π}(p_{2}), r_{π}(p_{1})). For example, below are the Poincaré polynomials of (SpF_{N}^{a})_{N∈[4]} (the cases N ∈ [3] are given by Figure 1):

S_{1}(q) = 1,
S_{2}(q) = q + 1,
S_{3}(q) = q^{2} + q + 1,
S_{4}(q) = q^{4} + 3q^{3} + 3q^{2} + 2q + 1.

We also defined natural varieties (SOF_{N}^{a})_{N≥1} [6], named orthogonal degenerate flag varieties, whose Poincaré polynomials O_{N} have the following combinatorial interpretation:

O_{N}(q) = ∑_{D∈SDC_{N}} q^{\overline{inv}(D)},

where \overline{inv}(D) equals ĩnv(D) minus the number of inversions of D of the kind (p, r_{π}(p)). For example, the Poincaré polynomials of (SOF_{N}^{a})_{N∈[4]} (the cases N ∈ [3] are given by Figure 1) are

O_{1}(q) = 1,
O_{2}(q) = 2,
O_{3}(q) = 2q + 1,
O_{4}(q) = 4q^{2} + 4q + 2.

The primary goal of this paper is to determine the cardinalities of the sets (SDC_{N})_{N≥1}. According to the parity of N, they appear in two sequences:

• (l_{n})_{n≥0} = (1, 1, 3, 21, …) \underline{A098278}; and

• (r_{n})_{n≥0} = (1, 2, 10, 98, …) \underline{A098279}

defined by Randrianarivony and Zeng [21] as specializations of polynomials interpolating median Euler numbers. We recall the necessary definitions below.

2.2 Extended median Euler numbers

Consider the family of polynomials (D_{n}(x))_{n≥0} defined by

D_{0}(x) = 1,
D_{n+1}(x) = (x + 1)(x + 2)D_{n}(x + 2) − x(x + 1)D_{n}(x) ∀n ≥ 0.

They were introduced by Randrianarivony and Zeng [21] as interpolations of the median Euler numbers (L_{n})_{n≥0} = (1, 1, 4, 46, …) \underline{A000657} and (R_{n})_{n≥0} = (1, 3, 24, 402, …) \underline{A002832}, through the equalities L_{n} = D_{n}(1/2) and R_{n} = D_{n}(−1/2).

It is easy to check that for n ≥ 1, the polynomial D_{n}(x) is of the form 2^{n}(x + 1)P_{n}(x + 1) for some polynomial P_{n}(x) of degree n−1 with positive integer coefficients. The polynomials P_{n}(x) satisfy the following recursive formulas:

P_{1}(x) = 1,
P_{n+1}(x) = \frac{(x + 2)(x + 1)}{2}P_{n}(x + 2) − \frac{x(x − 1)}{2}P_{n}(x) ∀n ≥ 1.

The first few such polynomials are

P_{1}(x) = 1,
P_{2}(x) = 2x + 1,
P_{3}(x) = 6x^{2} + 10x + 5,
P_{4}(x) = 24x^{3} + 84x^{2} + 110x + 49,
P_{5}(x) = 120x^{4} + 720x^{3} + 1758x^{2} + 1954x + 797.

For all n ≥ 1, let c_{n,n−1}x^{n−1} + c_{n,n−2}x^{n−2} + ⋯ + c_{n,1}x + c_{n,0} = P_{n}(x). It is easy to check the following recursive formulas: c_{1,0} = 1 and

c_{n,0} = ∑_{i=0}^{n−2} 2^{i}c_{n−1,i},  (1)

c_{n,k} = (k + 1)c_{n−1,k−1} + ∑_{i=k}^{n−2} 2^{i−k} (\binom{i + 1}{k} + 2\binom{i + 1}{k − 1}) c_{n−1,i},  (2)
c_{n,n−1} = nc_{n−1,n−2}  (3)

for all n ≥ 2 and k ∈ [n − 2]. In particular, we have c_{n,n−1} = n! for all n ≥ 1.

The sequences (l_{n})_{n≥0} = (1, 1, 3, 21, …) and (r_{n})_{n≥0} = (1, 2, 10, 98, …) are defined by l_{n} = D_{n}(0)/2^{n} and r_{n} = D_{n}(1)/2^{n} for all n ≥ 0, which, in terms of P_{n}, is equivalent to l_{0} = r_{0} = 1 and

l_{n} = P_{n}(1),
r_{n} = 2P_{n}(2) = 2P_{n+1}(0)

for all n ≥ 1. From Randrianarivony and Zeng [21, Théorème 24], it follows that

1 + ∑_{n≥1} xP_{n}(x)t^{n} = \frac{1}{1 − \frac{xt}{1 − \frac{(x + 1)t}{1 − \frac{2(x + 2)t}{1 − \frac{2(x + 3)t}{1 − \frac{3(x + 4)t}{1 − \frac{3(x + 5)t}{...}}}}}}} .

Afterwards, recall [10, 11, 12, 23] that a surjective pistol of size n is a surjective map f : [2n] ↠ {2, 4, 6, …, 2n} such that f(j) ≥ j for all j ∈ [2n]. Let SP_{n} be the set of the surjective pistols of size n. For all f ∈ SP_{n}, we denote by max(f) the number of maximal points of f (integers j ∈ [2n − 2] such that f(j) = 2n), and by fd(f) the number of doubled fixed points of f (integers j ∈ [2n − 2] such that there exists j′ < j with f(j′) = f(j) = j).

For example SP_{2} has three elements:

(\begin{matrix}1 & 2 & 3 & 4 \\ 2 & 2 & 4 & 4 \end{matrix}) , (\begin{matrix}1 & 2 & 3 & 4 \\ 4 & 2 & 4 & 4 \end{matrix}) and (\begin{matrix}1 & 2 & 3 & 4 \\ 2 & 4 & 4 & 4 \end{matrix}) ,

whose numbers of maximal points are respectively 0,1 and 1, and whose numbers of doubled fixed points are respectively 1,0 and 0.

Still due to Randrianarivony and Zeng [21, Proposition 25], it is known that

P_{n}(x) = ∑_{f∈SP_{n}} 2^{n−1−max(f)−fd(f)}x^{max(f)}  (4)

for all n ≥ 1. For example, considering the three elements of SP_{2} shown above, we indeed have the equality P_{2}(x) = 2x + 1 = 2^{1−0−1}x^{0} + 2^{1−1−0}x^{1} + 2^{1−1−0}x^{1}.

2.3 Even symmetric Dellac configurations

One of the goals of this paper is to give a new proof of the statement that the cardinality of SDC_{2n} (for n ≥ 1) is the number r_{n} from the sequence (r_{n})_{n≥0} = (1, 2, 10, 98, 1594, …) (another proof can be found in a previous paper [2]). The first step in this direction is to reduce SDC_{2n} to smaller elements that we name even extended Dellac configurations, whose set is denoted by T_{n}^{e}. The main result of this section is Theorem 7, which interprets P_{n}(x) combinatorially in terms of T_{n}^{e}, and which implies the equality |SDC_{2n}|= 2P_{n}(2) = r_{n}.

2.3.1 Generation of SDC_{2n}

An even extended Dellac configuration T ∈ T_{n}^{e} is a tableau made up of n columns and 2n rows, which contains 2n points (one per row, two per column) on or above the line y = x (in other words, this is the definition of DC_{n}, except that we remove the condition that the points must be under the line y = n + x). By considering the two points of the last column (from left to right) of a tableau T ∈ T_{n}^{e}, it is easy to obtain the formula |T_{n}^{e}|= \frac{(n+1)n}{2}|T_{n−1}^{e}|= (n + 1)! n! /2^{n}. For example, in Figure 2 we represent the 3 elements of T_{2}^{e}. Note that the points located on or above the line y = 2n − x (represented by a dashed line) are represented by stars; in general, we name such points free points, and we denote the number of free points of T ∈ T_{n}^{e} by fr(T). In Figure 2, the numbers of free points are 2, 1 and 2 from left to right.

There exists a one-to-one correspondence between SDC_{2n} and the set of tableaux T ∈ T_{n}^{e} whose free points are labeled with the number 0 or 1. For such a tableau T, the principle is:

\begin{matrix}⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 2: The 3 elements of T_{2}^{e}.

• to draw an empty tableau T̃ made up of 2n columns and 4n rows;

• for a box (j : i) of T containing a point p,

– if p is not free, or if p is a free point whose label is 1, then we draw a point in the box (j : i) of T̃;

– otherwise p is free and its label is 0, and we draw a point in the box (2n+1−j : i)

of T̃;

• to apply the central reflection with respect to the center (n, 2n) of T̃ to the 2n points

that have been drawn in T̃, which indeed makes T̃ an element of SDC_{2n}. For example, in Figure 3 we depict how a labeled tableau T_{0} ∈ T_{2}^{e} is mapped to its corresponding element T̃_{0} ∈ SDC_{4}.

\begin{matrix}0 \\ 1 \\ ⟶ \\ ⟶ \end{matrix}

Figure 3: Construction of an even symmetric Dellac configuration. This bijection between the tableaux T ∈ T_{n}^{e} whose free points are labeled with 0 or 1

and SDC_{2n} implies the following formula:

|SDC_{2n}|= ∑_{T ∈T_{n}^{e}} 2^{fr(T)}.  (5)

For example, for n = 2, the 10 = 2^{2} + 2^{1} + 2^{2} elements of SDC_{4} are generated by the 3 elements of T_{2}^{e} as depicted in Figure 4. The elements of SDC_{4} in the same frame under each tableau T ∈ T_{2}^{e} correspond to the 2^{fr(T)} different labellings of the free points of T.

\begin{matrix}⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 4: Construction of SDC_{4} from T_{2}^{e}.

2.3.2 A combinatorial interpretation of P_{n}(x) in terms of T_{n}^{e}

Definition 1. Let T ∈ T_{n}^{e}. For a given point p_{0} = (j : i) of T, we first define a path (p_{0}, p_{1}, …) of points of T as follows: for all k ≥ 0, assume that the points p_{0}, …, p_{k} are defined, and let (j_{k} : i_{k}) = p_{k};

(a) if j_{k} = n, then p_{k+1} is defined as p_{k};

(b) if j_{k} < n and p_{k} is the upper point of its column, then p_{k+1} is defined as p_{2n−j_{k}}^{T} (the point of the (2n − j_{k})-th row L_{2n−j_{k}}^{T} of T, see Section 1);

(c) if j_{k} < n and p_{k} is the lower point of its column, then p_{k+1} is defined as p_{j_{k}}^{T}.

We then define a finite subsequence S_{T} (i) = (p_{k_{0}}, …, p_{k_{f}}) of (p_{0}, p_{1}, …) by k_{0} = 0 and, if we assume that k_{0}, …, k_{q} are defined for some q ≥ 0,

• if j_{k_{q}} < max{j_{k} : k ≥ 0}, then k_{q+1} = min{k > k_{q} : j_{k} > j_{k_{q}}};

• otherwise f = q.

We finally define B(T) as S_{T} (n) and R(T) as S_{T} (2n). Let b(T) + 1 and r(T) + 1 be their respective number of elements.

For example, in Figure 5 we represent a tableau T_{1} ∈ T_{7}^{e} such that B(T_{1}) is the tuple ((2 : 7), (3 : 12), (7 : 11)) and R(T_{1}) is the tuple ((4 : 14), (7 : 10)). In general, when depicting a tableau T ∈ T_{n}^{e}, the first b(T) elements of B(T) and the first r(T) elements of R(T) are painted in blue and red respectively. The meaning of the green color in Figure 5 will be explained further (see Definition 4).

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 5: Extended Dellac configuration T_{1} ∈ T_{7}^{e} such that (b(T_{1}), r(T_{1}), g(T_{1})) = (2, 1, 1).

Definition 2. Let j ∈ [n]. We consider a tableau T made up of n columns (each of which contains at most two points) and 2n rows (each of which contains at most one point), such that each of the first j − 1 rows (from bottom to top) of T contains exactly one point on or above the line y = x, and each of the first j − 1 columns (from left to right) contains exactly two points (for example, any tableau T ∈ T_{n}^{e} satisfies this condition). Let i ∈ [j, 2n] be such that the first j − 1 boxes of the row L_{i}^{T} are empty (for example, any i ∈ [j, 2n] such that the box (j : i) of T contains a point). We define a sequence I_{T} (j : i) = (i_{0}, i_{1}, …) of elements of [2n] as follows: first of all, let i_{0} be the integer i, afterwards, if the integers i_{0}, …, i_{k} are defined for some k ≥ 0:

1. if i_{k} ∈ [j, 2n − j] ⊔ {2n}, then i_{k+1} is defined as i_{k};

2. if i_{k} ∈ [2n − j + 1, 2n − 1], let j_{k} = 2n − i_{k} ∈ [j − 1], then i_{k+1} is defined by (j_{k} : i_{k+1}) being the upper point of C_{j_{k}}^{T};

3. otherwise i_{k} ∈ [j − 1], and i_{k+1} is defined by (i_{k} : i_{k+1}) being the lower point of the C_{i_{k}}^{T}.

For example, in Figure 5, one can read the sequences corresponding to the free points p = (j : i) that appear in the red, blue or green path, by following the path in the opposite direction (…, p_{k}, p_{k−1}, …). We have I_{T_{1}}(7 : 10) = (10, 14, 14, …), I_{T_{1}}(7 : 11) = (11, 12, 13, 2, 7, 7, …), etc. The green path, as a subpath of the blue path, also gives I_{T_{1}}(2 : 13) = (13, 2, 2, …).

Proposition 3. In the context of Definition 2, the sequence I_{T} (j : i) = (i_{0}, i_{1}, …) becomes stationary, i.e., there exists an integer root_{T} (j : i) ∈ [j, 2n − j] ⊔ {2n} (named the root of the box (j : i) in T) and an integer k_{0} ≥ 0 such that i_{k} = root_{T} (j : i) for all k ≥ k_{0}. Moreover, the map i ↦ root_{T} (j : i) is a bijection from the set of integers i ∈ [j, 2n] such that the first j − 1 boxes of L_{i}^{T} are empty, to [j, 2n − j] ⊔ {2n}.

Proof. Since [2n] is a finite set, there exist 0 ≤ k_{1} < k_{2} such that i_{k_{1}} = i_{k_{2}}. Suppose that i_{k} ∉ [j, 2n − j] ⊔ {2n} for all k ≥ 0, i.e., the rule (i) of Definition 2 is never applied. Then, the sequence (i_{k})_{k≥0} is reversible: for all k > 0, let j_{k−1} ∈ [n] such that p_{i_{k}}^{T} = (j_{k−1} : i_{k}); if (j_{k−1} : i_{k}) is the upper point of its column, then i_{k−1} = 2n − j_{k−1}, otherwise i_{k−1} = j_{k−1}. This reversibility and the equality i_{k_{2}} = i_{k_{1}} imply i_{k_{2}−k_{1}} = i_{k_{1}−k_{1}} = i_{0} = i. Since k_{2} − k_{1} > 0 and, for all k > 0, the point p_{i_{k}}^{T} is of the kind (j_{k−1} : i_{k}) for some j_{k−1} ∈ [j −1], then the point p = (j : i) equals (j_{k_{2}−k_{1}−1} : i_{k_{2}−k_{1}}) for some j_{k_{2}−k_{1}−1} < j, which is absurd, so i_{k} belongs to [j, 2n − j] ⊔ {2n} for k big enough.

Let k_{min} be the smallest integer k ≥ 0 such that i_{k} = root_{T} (j : i). As stated in the previous paragraph, the sequence (i = i_{0}, i_{1}, …, i_{k_{min}}) is reversible because it never involves the rule (i) of Definition 2, so the map i ↦ root_{T} (j : i) is injective. Finally, the number of integers i ∈ [j, 2n] such that the first j − 1 boxes of L_{i}^{T} are empty is exactly the cardinality 2(n − j + 1) of the set [j, 2n − j] ⊔ {2n} (hence the map i ↦ root_{T} (j : i) is bijective): since the first j − 1 rows of T contain exactly j − 1 points, and the first j − 1 columns of T contain exactly 2(j − 1) points, then, among the 2n − j + 1 upper rows of T (the rows C_{j}^{T} , C_{j+1}^{T}, …, C_{2n}^{T}), exactly j − 1 of them contain a point in one of their first j − 1 boxes, so 2n − j + 1 − (j − 1) = 2(n − j + 1) of them have their first j − 1 boxes empty.

Definition 4. We define G(T) as the set of the free points p = (j : i) of T such that:

• the point other than p in C_{j}^{T} is an element of B(T);

• the integer root_{T} (j : i) equals j.

The cardinality of G(T) is denoted by g(T) and its elements are painted in green in the graphical representation of T.

For example, in Figure 5, we have G(T_{1}) = {(2 : 13)}.

Definition 5. Let n ≥ 1 and T ∈ T_{n}^{e}. We denote by Omax(T) (whose cardinality is omax(T)) the set of the elements of B(T), R(T) and G(T). Note that omax(T) ≥ 2. The set Max(T) (whose cardinality is max(T)) is defined as Omax(T) from which we removed the last element of B(T) and the last element of R(T). Hence

max(T) = b(T) + r(T) + g(T) = omax(T) − 2.

Remark 6. For all T ∈ T_{n}^{e}, the b(T) last points of B(T), the r(T) + 1 points of R(T), and the g(T) points of G(T), are pairwise distinct free points of T, so

fr(T) ≥ max(T) + 1.

The first main result of this paper is the following.

Theorem 7. For all n ≥ 1 we have

P_{n}(x) = ∑_{T ∈T_{n}^{e}} 2^{fr(T)−1−max(T)}x^{max(T)}.

For example, the three elements of T_{2}^{e} shown in Figure 6 give

P_{2}(x) = 2^{2−1−1−0−0}x^{1+0+0} + 2^{1−1−0−0−0}x^{0+0+0} + 2^{2−1−0−1−0}x^{0+1+0} = 2x + 1.

\begin{matrix}⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 6: The three elements of T_{2}^{e}.

The cardinality of SDC_{2n} being r_{n} = 2P_{n}(2) is then obtained by setting x = 2 in Theorem 7 in view of Formula (5). Section 3 is dedicated to the proof of Theorem 7 (by induction, using the recursive formulas (1), (2) and (3)). Remark 8. An independent proof of |SDC_{2n}|= r_{n} is given in a previous paper [2]. The proof is based on a surjection φ : T_{n}^{e} ↠ SP_{n} such that

2^{n−fd(f)} = ∑_{T ∈φ^{−1}(f)} 2^{fr(T)}  (6)

for all f ∈ SP_{n}, which proves |SDC_{2n}|= 2P_{n}(2) = r_{n} in view of Formula (4) and Formula (5). Afterwards, one can check that for all f ∈ SP_{n} and T ∈ φ^{−1}(f),

1. g(T) is the number of integers j ∈ {2, 4, …, 2n − 2} such that f(j − 1) = f(j) = 2n and min{j′ < j − 1 : f(j′) = j} is even;

2. r(T) is the number of all other integers j ∈ {2, 4, …, 2n − 2} such that f(j) = 2n;

3. b(T) is the number of integers j ∈ {1, 3, …, 2n − 3} such that f(j) = 2n.

It follows that max(f) = max(T), which proves Theorem 7 by Formula (4) and Formula (6).

2.4 Odd symmetric Dellac configurations

A second goal of this paper is to prove that the cardinality of SDC_{2n−1}(n ≥ 1) is the number l_{n} from the sequence (l_{n})_{n≥0} = (1, 1, 3, 21, 267, …) introduced in Section 2.2. It is obviously true for n = 1 (see Figure 1). Afterwards, as we did for the even case, we reduce SDC_{2n−1}(n ≥ 2) to smaller elements called odd extended Dellac configurations, whose set is denoted by T_{n−1}^{o}. In Theorem 10, we give a combinatorial interpretation of P_{n}(x) in terms of T_{n−1}^{o}, which implies the equality |SDC_{2n−1}|= P_{n}(1) = l_{n}.

2.4.1 Generation of SDC_{2n+1}(n ≥ 1)

We define odd extended Dellac configurations T ∈ T_{n}^{o} (n ≥ 1) as the tableaux T of size n × (2n + 1) with the following conditions:

• each column of T contains exactly two points;

• each row of T contains at most one point;

• each of the first n rows of T contains exactly one point.

In other words, a tableau T ∈ T_{n}^{o} is like an element of T_{n}^{e}, except that it has 2n + 1 rows instead of 2n, and exactly one of its n + 1 upper rows is empty (i.e., has no points). There is a natural surjection ϕ : T_{n}^{o} ↠ T_{n}^{e} which consists in deleting the empty row of the elements of T_{n}^{o}, and it is clear that |ϕ^{−1}(T)|= n + 1 for all T ∈ T_{n}^{e}. Hence |T_{n}^{o}|= (n + 1)|T_{n}^{e}|= ((n + 1)! )^{2}/2^{n}. For example, the 9 elements of T_{2}^{o} are surjected into the 3 elements of T_{2}^{e} as shown in Figure 7.

\begin{matrix}⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ → \\ ⋆ \\ ⋆ \\ , \\ ⋆ \\ ⋆ \\ ⋆ \\ → \\ ⋆ \\ , \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ → \\ ⋆ \\ ⋆ \\ . \end{matrix}

Figure 7: A surjection from T_{2}^{o} to T_{2}^{e}.

For a tableau T ∈ T_{n}^{o}, we represent with stars the points of T located on or above the line y = 2n + 1 − x (dashed line). We call these points free points of T and denote their number by fr(T).

Similarly as for SDC_{2n}, the odd symmetric Dellac configurations D ∈ SDC_{2n+1} are in one-to-one correspondence with the elements of T_{n}^{o} whose free points are labeled with the integers 0 or 1: for such a tableau T, we construct the corresponding element of SDC_{2n+1} as follows:

• we draw an empty tableau \overline{T} made up of 2n + 1 columns and 4n + 2 rows; • for a box (j : i) of T containing a point p,

– if p is not free, or if p is a free point whose label is 1, then we draw a point in the box (j : i) of \overline{T};

– otherwise p is free and its label is 0, and we draw a point in the box (2n+2−j : i) of \overline{T};

• we draw a point in the box (n + 1 : i_{0}) where L_{i_{0}}^{T} is its unique empty row;

• we apply the central reflexion with respect to the center (n + 1/2, 2n + 1) of \overline{T} to the 2n+1 points that have been drawn in \overline{T}, which indeed makes \overline{T} an element of SDC_{2n+1}.

For example, we depict in Figure 8 how a labeled tableau T_{2} ∈ T_{2}^{o} is mapped to its corresponding element \overline{T_{2}} ∈ SDC_{5}.

\begin{matrix}1 \\ 0 \\ ⟶ \\ ⟶ \end{matrix}

Figure 8: Construction of an odd symmetric Dellac configuration.

This bijection between the tableaux T ∈ T_{n}^{o} whose free points are labeled with 0 or 1 and SDC_{2n+1} implies the following formula for all n ≥ 1:

|SDC_{2n+1}|= ∑_{T ∈T_{n}^{o}} 2^{fr(T)}.  (7)

For example, for n = 1, the 3 = 2^{0} + 2^{1} elements of SDC_{3} are generated by the 2 elements of T_{2}^{o} as depicted in Figure 9, where the elements of SDC_{3} in the same frame under every T ∈ T_{1}^{o} correspond to the 2^{fr(T)} different labellings of the free points of T.

2.4.2 A combinatorial interpretation of P_{n}(x) in terms of T_{n−1}^{o}

We adapt Definition 1, Definition 2, Proposition 3 and Definition 4 to tableaux T ∈ T_{n}^{o} as follows:

• first of all, we replace all the occurrences of 2n with 2n + 1, which does not change the proof of Proposition 3;

\begin{matrix}⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 9: Construction of SDC_{3} from T_{1}^{o}.

• regarding S_{T} (i) from Definition 1, if L_{i}^{T} is its unique empty row, then S_{T} (i) is defined as the empty sequence; otherwise, if the points p_{0}, …, p_{k_{0}} are defined for some k_{0} ≥ 0, and if the rule b) or the rule c) involves the unique empty row of T, then we define p_{k} as p_{k_{0}} for all k > k_{0};

• in Definition 1, instead of R(T) and B(T), we define a single finite sequence V (T) = S_{T} (2n + 1) (possibly empty), whose number of elements is denoted by v(T);

• the set G(T) is defined by replacing B(T) with V (T) in Definition 4.

For example, in Figure 10 we represent a tableau T_{3} ∈ T_{6}^{o} such that V (T_{3}) is the tuple ((2 : 13), (3 : 11), (4 : 10)) and G(T_{3}) = {(2 : 12)}. In general, when depicting a tableau T ∈ T_{n}^{o}, the v(T) elements of V (T) and the g(T) elements of G(T) are painted in purple and green respectively.

Remark 9. For all T ∈ T_{n−1}^{o}, the v(T) elements of V (T) and the g(T) elements of G(T) are pairwise distinct free points, so fr(T) ≥ v(T) + g(T).

The second main result of this paper is the following.

Theorem 10. For all n ≥ 2,

P_{n}(x) = ∑_{T ∈T_{n−1}^{o}} 2^{fr(T)−g(T)}x^{v(T)}(1 + x)^{g(T)}.

For example, the two elements of T_{1}^{o} shown in Figure 11 give

P_{2}(x) = 2^{0−0}x^{0}(1 + x)^{0} + 2^{1−0}x^{1}(1 + x)^{0} = 2x + 1,

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 10: Odd extended Dellac configuration T_{3} ∈ T_{6}^{o} such that (v(T_{3}), g(T_{3})) = (3, 1). and the nine elements of T_{2}^{o} shown in Figure 12 give

P_{3}(x) = 2^{1−0}x^{0}(1 + x)^{0} + 2^{1−0}x^{1}(1 + x)^{0} + 2^{2−1}x^{1}(1 + x)^{1}

+ 2^{1−0}x^{0}(1 + x)^{0} + 2^{1−0}x^{1}(1 + x)^{0} + 2^{1−0}x^{1}(1 + x)^{0} + 2^{0−0}x^{0}(1 + x)^{0} + 2^{1−0}x^{1}(1 + x)^{0} + 2^{2−0}x^{2}(1 + x)^{0} = 2 + 2x + 2x(1 + x) + 2 + 2x + 2x + 1 + 2x + 4x^{2} = 6x^{2} + 10x + 5.

⋆

Figure 11: The two elements of T_{1}^{o}.

\begin{matrix}⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 12: The nine elements of T_{2}^{o}.

The cardinality of SDC_{2n−1} being P_{n}(1) = l_{n} for all n ≥ 2 is then obtained by setting x = 1 in Theorem 10, in view of Formula (7). Section 4 is dedicated to the proof of Theorem 10.

3 Proof of Theorem 7

For all n ≥ 1, let

E_{n}(x) = ∑_{T ∈T_{n}^{e}} 2^{fr(T)−1−max(T)}x^{max(T)}.

By Remark 6 and the inequality fr(T) ≤ n for all T ∈ T_{n}^{e} (the free points of T are of the kind (j : i) such that 2n ≥ i ≥ 2n + 1 − j ≥ n + 1, and hence are located in the n top rows), the polynomial E_{n}(x) has positive integers coefficients and its degree is at most n − 1. Moreover, if we define T_{n,max} ∈ T_{n}^{e} as the tableau whose points are (j : j) and (j : 2n+1−j) for all j ∈ [n] (see Figure 13 for the case n = 4), then b(T_{n,max}) = 0, r(T_{n,max}) = n − 1 and g(T_{n,max}) = 0, so max(T_{n,max}) = n − 1, which makes the degree of E_{n}(x) exactly n − 1.

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 1 \\ 2 \\ 3 \\ 4 \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 13: The tableau T_{4,max} ∈ T_{4}^{e}.

For all k ∈ [0, n − 1], let T_{n,k}^{e} be the set of the tableaux T ∈ T_{n}^{e} such that max(T) = k,

and let e_{n,k} = ∑_{T ∈T_{n,k}^{e}} 2^{fr(T)−1−k}, so that

E_{n}(x) = ∑_{k=0}^{n−1} e_{n,k}x^{k}.

Theorem 7 states that E_{n}(x) = P_{n}(x), i.e., that e_{n,k} = c_{n,k} for all k ∈ [0, n − 1]. It is clear that e_{1,0} = 1 = c_{1,0}. We will prove the rest by checking that (e_{n,k})_{0≤k≤n} satisfies the recursive formulas (1) ,(2),(3). To do so, we first define in the next section a surjection from T_{n}^{e} to T_{n−1}^{e}.

3.1 A surjection Π : T_{n}^{e} ↠ T_{n−1}^{e}(n ≥ 2)

Consider T ∈ T_{n}^{e} and the integers (j_{n−1}, j_{n+1}) ∈ [n]^{2} such that the points of L_{n−1}^{T} and L_{n+1}^{T} are located in C_{j_{n−1}}^{T} and C_{j_{n+1}}^{T} respectively. We define (i_{min}, i_{max}) as (n − 1, n + 1) if j_{n−1} ≤ j_{n+1}, as (n + 1, n − 1) otherwise.

We define two new paths

(B′(T), R′(T)) = \begin{cases}(S_{T} (i_{min}), S_{T} (i_{max})), & if C_{n−1}^{T} contains an element of R(T); \\ (S_{T} (i_{max}), S_{T} (i_{min})), & if C_{n−1}^{T} contains an element of G(T); \\ (S_{T} (n + 1), S_{T} (n − 1)), & otherwise and if p_{n+1}^{T} is free; \\ (S_{T} (n − 1), S_{T} (n + 1)), & otherwise. \end{cases}

We also define a new set G′(T): the set of the free points of T of the kind p = (j : i) such that the other point of C_{j}^{T} is an element of B′(T), and such that root_{T} (j : i) = j. Their respective numbers of elements located in C_{1}^{T} , C_{2}^{T} , …, C_{n−1}^{T} are denoted by b′(T), r′(T) and g′(T). Note that S_{T} (n + 1) = ((n : n + 1)) for all tableau T in which p_{n+1}^{T} is free, so r′(T) or b′(T) may equal 0. However, the first element of S_{T} (n − 1), the point p_{n−1}^{T}, is always of the kind (j : n − 1) for some j < n, so b′(T) + r′(T) ≥ 1 in general. The set of the elements of B′(T), R′(T) or G′(T) is denoted by Max′(T) whose cardinality is max′(T) = b′(T) + r′(T) + g′(T). For example, consider the tableau T_{1} ∈ T_{7}^{e} from Figure 5, we depict in Figure 14 the paths B′(T_{1}) = ((5 : 6), (6 : 9)) and R′(T_{1}) = ((6 : 8)) by painting them in light blue and orange respectively (there the set G′(T_{1}) is empty).

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 14 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 14: The tableau T_{1} ∈ T_{7}^{e}, with b′(T_{1}) = 2, r′(T_{1}) = 1 and g′(T_{1}) = 0.

In order to construct an element Π(T) of T_{n−1}^{e} from T ∈ T_{n}^{e}, we “project” all points of T that are not elements of Max(T) or Max′(T) in a tableau (n − 1) × (2n − 2), then we construct Max(Π(T)) as a “union” of Max(T) and Max′(T), in a meaning that we will make explicit.

Definition 11. Consider an integer j ∈ [n] and a tableau T that satisfies the conditions of Definition 2. Let i_{f} ∈ [j, 2n − j] ⊔ {2n} and let i_{0} ∈ [j, 2n] be the unique integer such that root_{T} (j : i_{0}) = i_{f} in view of Proposition 3. We define the insertion of a point in the box (j : i_{f}) of T as the plotting of a point in the box (j : i_{0}).

Note that if L_{i_{f}}^{T} has its first j − 1 boxes empty, then i_{0} = i_{f}.

For example, if T is a 7 × 14 tableau whose first column is the same as in Figure 14, then the insertions of points in the boxes (2 : 2) and (2 : 7) of T result in plotting points in the boxes (2 : 13) and (2 : 7) of T respectively.

In general, let us now label the points of Max(T) and Max′(T) with letters ρ, β or γ. The points labeled with β (respectively ρ, γ) will correspond to the elements of B(Π(T)) (respectively R(Π(T)), G(Π(T))).

Definition 12. Let T ∈ T_{n}^{e}(n ≥ 2). We label the elements of Max(T) and Max′(T) as follows.

• If a point p_{1} belongs to B(T) (respectively R′(T)) and the other point p_{2} in the same column belongs to B′(T) (respectively R(T)), then we label p_{1} with β and p_{2} with γ.

• If a point p belongs to B(T) or B′(T) (respectively R(T) or R′(T), G(T) or G′(T)) and p doe not meet the first rule, then we label p with β (respectively ρ, γ).

Definition 13 (Map Π : T_{n}^{e} → T_{n−1}^{e}). Let T ∈ T_{n}^{e}. We first define a tableau Π_{0}(T), made up of n − 1 columns and 2n − 2 rows, such that for all points p = (j : i) of T that does not belong to Max(T) or Max′(T) (in particular j < n and i ∉ {n, n + 1}), the tableau Π_{0}(T) contains a point in its box (j : ĩ) where the integer ĩ is defined by

ĩ = \begin{cases}i, & if i < n; \\ i − 2, & if i > n + 1. \end{cases}

For example, for the tableau T_{1} ∈ T_{7}^{e} depicted in Figure 14, we obtain the tableau Π_{0}(T_{1}) of Figure 15. Afterwards, let X_{T} be the empty set. For j from 1 to n − 1, if C_{j}^{T} contains a point p labeled with β (respectively ρ, γ), we insert a point in the box (j : n − 1) of Π_{0}(T) (respectively the box (j : 2n − 2), the box (j : j)), following Definition 11. We say that we have inserted p in Π_{0}(T). Also, if p ∈ Max(T), let p_{new} be the point that we just plotted in Π_{0}(T) following the latter insertion, then we add p_{new} to X_{T}.

Let Π(T) be the tableau obtained at the end of this algorithm. It is straightforward by Definition 11 that Π(T) is an element of T_{n−1}^{e}, and that X_{T} ⊊ Omax(Π(T)) (it is not equal because the point p_{n−1}^{Π(T)} is an element of Omax(Π(T)) that results from the insertion in Π_{0}(T) of the point p_{n−1}^{T}, but p_{n−1}^{T} belongs to Max′(T), not to Max(T). Hence p_{n−1}^{Π(T)} ∉ X_{T}). The set X_{T} will be useful to reconstruct T from Π(T) (see Proposition 20).

1 2 3 4 5 6 7 8 9 10 11 12 1 2 3 4 5 6

Figure 15: The tableau Π_{0}(T_{1}).

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \\ ⋆ \end{matrix}

Figure 16: The tableau Π(T_{1}) ∈ T_{6}^{e}.

For example, the tableau Π(T_{1}) ∈ T_{6}^{e} is as depicted in Figure 16, and X_{T_{1}} is the tuple {(2 : 6), (2 : 11), (3 : 10), (4 : 12)}.

Note that (b(Π(T_{1})), r(Π(T_{1})), g(Π(T_{1}))) = (3, 1, 1).

Remark 14. For all T ∈ T_{n}^{e}, we have

max(Π(T)) = max(T) + max′(T) − 2.

Indeed, the insertions in Π_{0}(T) of the two points of C_{n−1}^{T}, which both belong to Max(T) or Max′(T) (because their roots belong to {n − 1, n, n + 1, 2n}), produce the two points of C_{n−1}^{Π(T)}, in other words, the last element of B(Π(T)) and the last element of R(Π(T)), which are not counted by the statistics b and r.

In particular, since max′(T) ≥ 1 in general (the set Max′(T) always contains p_{n−1}^{T}), we have

max(Π(T)) ∈ [max(T) − 1, n − 2].

For example, for the tableau T_{1} ∈ T_{7}^{e}, we obtain max(Π(T_{1})) = (2+1+1)+(2+1)−2 = 5.

We now intend to construct Π^{−1}(T_{0}) for all T_{0} ∈ T_{n−1}^{e}. To do so, we first need to define labels for the elements of Omax(T_{0}), given a subset X ⊊ Omax(T_{0}).

Definition 15. For a tableau T_{0} ∈ T_{n−1}^{e} and a subset X ⊊ Omax(T_{0}), let us define labels of the elements of Omax(T_{0}) as follows.

• For all points p ∈ G(T_{0}), let q ≠ p be the other point of the column of p (the point q is then an element of B(T_{0})).

– If neither p nor q belong to X, we label p and q with the respective letters 𝔤′ and 𝔟′.

– If only q belongs to X, we label p and q with the respective letters 𝔟′ and 𝔟.

– If only p belongs to X, we label p and q with the respective letters 𝔯 and 𝔯′.

– If both p and q belong to X, we label p and q with the respective letters 𝔤 and 𝔟.

• For all points p among the first b_{0}(T) elements of B(T_{0}) (respectively among the first r(T_{0}) elements of R(T_{0})) that are not covered by the first case, if p ∉ X, then we label p with 𝔟′ (respectively 𝔯′), otherwise we label p with 𝔟 (respectively 𝔯).

• Let p^{b} (respectively p^{r}) be the last element of B(T_{0}) (respectively of R(T_{0})). Recall that p^{b} and p^{r} are the two points of C_{n−1}^{T_{0}}.

– If p^{r} ∉ X, we label p^{r} with the letter 𝔯′. Afterwards, we label p^{b} with the letter 𝔟′ if p^{b} ∉ X, with the letter 𝔟 otherwise.

– Otherwise, let j_{min} be the smallest integer j ∈ [n − 1] such that C_{j}^{T_{0}} contains an element of Omax(T_{0})\X. If j_{min} = n − 1, then Omax(T_{0}) = {p^{b}, p^{r}} and hence X = {p^{r}}, and we label p^{b} and p^{r} with the respective letters 𝔟′ and 𝔯. If j_{min} < n − 1, all the elements of Omax(T_{0}) that appear in C_{j_{min}}^{T_{0}} have already been labeled. We then have two cases:

∗ If C_{j_{min}}^{T_{0}} contains an element labeled with 𝔟′, then we label p^{r} with the letter 𝔯. Afterwards, we label p^{b} with the letter 𝔟′ if p^{b} ∉ X, with the letter 𝔟 otherwise.

∗ Otherwise, we label p^{b} and p^{r} with the respective letters 𝔯′ and 𝔯 if p^{b} ∉ X, with the respective letters 𝔟 and 𝔤 otherwise.

Remark 16. In the context of Definition 15, the elements of Omax(T_{0}) that are labeled with 𝔟, 𝔯 or 𝔤 are exactly the elements of X.

Definition 17. Let i ∈ [0, n − 2], and T_{0} ∈ T_{n−1,i}^{e}. We consider a subset X ⊊ Omax(T_{0}), whose cardinality |X| is denoted by k. Note that omax(T_{0}) = i + 2 hence k ∈ [0, i + 1]. We intend to define a set 𝔗(T_{0}, X) ⊂ T_{n}^{e} whose cardinality is either 1 or 2 following three situations described below. Consider the labels introduced in Definition 15.

1. Let S_{1} be the situation where k ≤ i and no point of the last column C_{n−1}^{T_{0}} of T_{0} is labeled with 𝔯 or 𝔤.

2. Let S_{2} be the situation where:

• either k = i + 1;

• or one of the points of C_{n−1}^{T_{0}} is labeled with 𝔯 or 𝔤, and there are no two elements of Omax(T_{0})\X labeled with 𝔟′ and 𝔯′.

3. Let S_{3} be the remaining situation, i.e., where k ≤ i, one of the points of C_{n−1}^{T_{0}} is labeled with 𝔯 or 𝔤, and there exist two elements of Omax(T_{0})\X labeled with 𝔟′ and 𝔯′.

In any situation of the three above situations, first consider a n×2n tableau 𝔗_{0}(T_{0}) containing points only in its boxes (j : \overline{i}) for all points (j : i) of T_{0} that does not belong to Omax(T_{0}), where \overline{i} is defined as i if i < n, as i + 2 otherwise. Let us set T^{1} = T^{2} = T^{3/} = T^{3\} = 𝔗_{0}(T_{0}). For j from 1 to n − 1, assume that C_{j}^{T_{0}} contains an element p ∈ Omax(T_{0}) (otherwise T^{1}, T^{2}, T^{3/}, T^{3\} already contain two points in their j-th columns and we do nothing).

• If the label of p is 𝔟 (respectively 𝔯, 𝔤, 𝔤′), we insert a point in the box (j : n) (respectively (j : 2n), (j : j), (j : j)) of T^{1}, T^{2}, T^{3/} and T^{3\}.

• If the label of p is 𝔟′ (respectively 𝔯′),

– in the situation S_{1}, we insert a point in the box (j : n−1) (respectively (j : n+1)) of T^{1}; – in the situation S_{2}, we insert a point in the box (j : n − 1) of T^{2};

– in the situation S_{3},

∗ if the points of the last column of T_{0} have the labels 𝔯′ and 𝔯, or 𝔟 and 𝔤, then we insert a point in the box (j : n + 1) (respectively (j : n − 1)) of T^{3/}, and we insert a point in the box (j : n − 1) (respectively (j : n + 1)) of T^{3\};

∗ otherwise, we insert a point in the box (j : n − 1) (respectively (j : n + 1)) of T^{3/}, and we insert a point in the box (j : n + 1) (respectively (j : n − 1)) of T^{3\}.

We say that we inserted p in T^{1} (respectively T^{2}, T^{3/} and T^{3\}) in the situation S_{1} (respectively S_{2}, S_{3}). At the end of this algorithm, we finally insert two points in the boxes (n : n) and (n : 2n) of T^{1} (respectively T^{2}, T^{3/} and T^{3\}) in the situation S_{1} (respectively S_{2}, S_{3}).

The choice of T_{0} and X ⊊ Omax(T_{0}) results in one of the three situations S_{1}, S_{2}, S_{3}, depending on whether T^{1}, or T^{2}, or both T^{3/} and T^{3\} belong to T_{n}^{e} at the end of the above algorithm. Let 𝔗(T_{0}, X) ⊂ T_{n}^{e} be defined as {T^{1}} (respectively {T^{2}}, {T^{3/}, T^{3\}}) in the situation S_{1} (respectively S_{2}, S_{3}).

Remark 18. If T ∈ 𝔗(T_{0}, X), then by construction the cardinality of Max(T) is the number of points of Omax(T_{0}) labeled with 𝔟, 𝔯 or 𝔤, in other words it equals the cardinality k of X by Remark 16, and 𝔗(T_{0}, X) ⊂ T_{n,k}^{e}. Remark 19. In the context of Definition 17, if a tableau is defined in the situation S_{1} or S_{3}, then the point p_{n+1}^{T} is not free, in other words the box (n : n + 1) of T is empty, whereas in the situation S_{2} the point p_{n+1}^{T} is (n : n + 1) hence is free. Indeed, in the situation S_{1}, the points of C_{n−1}^{T_{0}} have the labels 𝔟′ and 𝔯′, so the points of C_{n−1}^{T} are obtained by inserting two points in the boxes (n − 1 : n − 1) and (n − 1 : n + 1) of T^{1}, which implies that p_{n+1}^{T} is located in the first n − 1 columns of T and p_{n+1}^{T} is then not free; in the situation S_{3}, since there exists two elements of Omax(T_{0})\X with the labels 𝔟′ and 𝔯′, by construction we insert a point in boxes (j_{1} : n − 1) and (j_{2} : n + 1) for some j_{1}, j_{2} < n in both tableaux T^{3/} and T^{3\}, so p_{n+1}^{T} is also not free; finally, in the situation S_{2}, we never insert a point in any box (j : n + 1) for all j < n, so p_{n+1}^{T} is necessarily located in C_{n}^{T} hence is free.

Let us now compare the number fr(T_{0}) to the numbers fr(T) for all T ∈ 𝔗(T_{0}, X). First of all, note that fr(T_{0}) equals the number of free points located in 𝔗_{0}(T_{0}) (which we denote by fr_{0}(T_{0})), and that omax(T_{0}) − 1 = i + 1 in view of Remark 6. Likewise, if T ∈ 𝔗(T_{0}, X), by construction

fr(T) = fr_{0}(T_{0}) + (max(T) + 1) + max′(T) − η

where η is the number of non-free points of Max′(T), i.e., η = 1 if p_{n+1}^{T} is free (in which case p_{n−1}^{T} is the only non-free point of Max′(T)), which happens exactly in the situation S_{2}, or η = 2 otherwise, in the situations S_{1} and S_{3}. Since max(T) = k (in view of Remark 18) and max′(T) = omax(T_{0}) − |X|= i + 2 − k by construction, we then have

\begin{cases}fr(T) = fr_{0}(T_{0}) + i + 3 − 2 = fr(T_{0}), & in the situation S_{1} or S_{3}; \\ fr(T) = fr_{0}(T_{0}) + i + 3 − 1 = fr(T_{0}) + 1, & in the situation S_{2}. \end{cases}

Proposition 20. For all i ∈ [0, n − 2] and T_{0} ∈ T_{n−1,i}, we have Π^{−1}(T_{0}) ⊂ ⨆_{k=0}^{i+1} T_{n,k}^{e}, and for all k ∈ [0, i + 1],

Π^{−1}(T_{0}) ∩ T_{n,k}^{e} = ⨆_{\begin{matrix}X⊂Omax(T_{0}), \\ |X|=k \end{matrix}} 𝔗(T_{0}, X).  (8)

Therefore Π is surjective.

Proof. Let T ∈ T_{n}^{e}, if Π(T) = T_{0}, then i ∈ [max(T) − 1, n − 2] by Remark 6. Hence we have Π^{−1}(T_{0}) ⊂ ⨆_{k=0}^{i+1} T_{n,k}^{e}.

Let us now prove that the elements T ∈ 𝔗(T_{0}, X) for all X ⊊ Omax(T_{0}) are indeed mapped to T_{0} by Π. It is straightforward that Π_{0}(T) is obtained by erasing all the elements of Omax(T_{0}) from T_{0}. Afterwards, for a point p ∈ Omax(T_{0}), let p̄ ∈ Max(T) ⊔ Max′(T) be the point of T obtained by inserting p in 𝔗_{0}(T_{0}). One can check that the label of p̄ as defined by Definition 12 is β (respectively ρ, γ) if and only if p ∈ B(T_{0}) (respectively p ∈ R(T_{0}), G(T_{0})), so we obtain the equality Π(T) = T_{0} and the inclusion 𝔗(T_{0}, X) ⊂ Π^{−1}(T_{0}).

Reciprocally, for all T ∈ Π^{−1}(T_{0}), we show that T ∈ 𝔗(T_{0}, X_{T}). It is straightforward that 𝔗_{0}(T_{0}) is obtained by erasing all the elements of Omax(T) and Max′(T) from T. Afterwards, for a point p ∈ Max(T) ⊔ Max′(T), let p̃ ∈ Omax(T_{0}) be the point of T_{0} that was obtained by inserting p in in Π_{0}(T). One can check that if p ∈ B(T) (respectively p ∈ R(T), G(T), B′(T), R′(T), G′(T)), then the label of p̃ as defined by Definition 15 with X = X_{T} (recall that X_{T} is defined at the same time as Π(T) in Definition 13) is 𝔟 (respectively 𝔯, 𝔤, 𝔟′, 𝔯′, 𝔤′). Consequently, if 𝔗(T_{0}, X_{T}) is defined in the situation S_{1} or S_{2}, then 𝔗(T_{0}, X_{T}) = {T }. If 𝔗(T_{0}, X_{T}) is defined in the situation S_{3}, then 𝔗(T_{0}, X_{T}) = {T^{3/}, T^{3\}} where T = T^{3/} if i_{min}^{T} = n − 1, otherwise T = T^{3\}.

So Π^{−1}(T_{0}) = ⨆_{X⊊Omax(T_{0})} 𝔗(T_{0}, X). Formula (8) then follows from Remark 18.

Lemma 21. Let T_{0} ∈ T_{n−1}^{e}, X ⊊ Omax(T_{0}) and T ∈ 𝔗(T_{0}, X). The following assertions are equivalent.

(i) The set 𝔗(T_{0}, X) is defined in the situation S_{1} of Definition 17.

(ii) The point p_{n+1}^{T} is not free and no point of C_{n−1}^{T} is an element of R(T) or G(T).

(iii) The set X does not contain the last element p^{r} of R(T_{0}), and |X|≤ max(T_{0}).

Proof. The equivalence (i) ⇔ (iii) is straightforward by the third point of Definition 15.

Let us prove that (i) implies (ii). Suppose that 𝔗(T_{0}, X) is defined in the situation S_{1} of Definition 17, and hence 𝔗(T_{0}, X) = {T }. We know that max(T) = |X|≤ max(T_{0}) by hypothesis, so max′(T) = omax(T_{0}) − |X|≥ 2. Now, as stated in the proof of Proposition 20, the hypothesis that no point of C_{n−1}^{T_{0}} has the label 𝔯 or 𝔤 implies that no point of C_{n−1}^{T} belongs to R(T) or G(T). It remains to prove that p_{n+1}^{T} is not free. In general, by Proposition 3, the roots of the points of C_{n−1}^{T} belong to {n − 1, n, n + 1, 2n}. Since no point of C_{n−1}^{T} belongs to R(T) by hypothesis, their roots cannot be 2n. If a point p of C_{n−1}^{T} has the root n + 1, then obviously p_{n+1}^{T} is located in one of the first n − 1 columns of T, so p_{n+1}^{T} is not free.

Otherwise, one point p ∈ C_{n−1}^{T} has the root n − 1 and the other point q of C_{n−1}^{T} has the root n. It implies that q is an element of B(T). Since no point of C_{n−1}^{T} belongs to R(T) or G(T), in particular p ∉ G(T), so p cannot be free by definition of G(T). It follows that p = (n − 1 : n − 1) and S_{T} (n − 1) = (p). Since max′(T) ≥ 2, the sequence S_{T} (n + 1) has at least one element located in the first n − 1 columns of T, in other words p_{n+1}^{T} (the first element of S_{T} (n + 1)) is not free. So (i) implies (ii).

Let us now prove that (ii) implies (i). If p_{n+1}^{T} is not free and no point of C_{n−1}^{T} belongs to R(T) or G(T), as stated in the proof of Proposition 20, no point of C_{n−1}^{T} has the label 𝔯 or 𝔤. Also, since max′(T) ≥ 2 because Max(T) contains p_{n−1}^{T} in general, and p_{n+1}^{T} in this case (because p_{n+1}^{T} is not free), we have |X|= max(T) = omax(T_{0}) − max′(T) = max(T_{0}) + 2 − max′(T) ≤ max(T_{0}). So (ii) implies (i).

Lemma 22. Let T_{0} ∈ T_{n−1}^{e}, X ⊊ Omax(T_{0}) and T ∈ 𝔗(T_{0}, X). The following assertions are equivalent.

(i) The set 𝔗(T_{0}, X) is defined in the situation S_{2} of Definition 17.

(ii) The point p_{n+1}^{T} is free.

(iii) If |X|< max(T_{0}) + 1, then the last element p^{r} of R(T_{0}) belongs to X, and no two elements of Omax(T_{0})\X are labeled with 𝔟′ and 𝔯′.

Proof. The equivalence (i) ⇔ (iii) is straightforward by the third point of Definition 15.

Let us prove that (i) implies (ii). Suppose that 𝔗(T_{0}, X) is defined in the situation S_{2} of Definition 17, and hence 𝔗(T_{0}, X) = {T }. If |X|= max(T_{0}) + 1, then max′(T) = omax(T_{0}) − |X|= 1, so Max′(T) = {p_{n−1}^{T}} and p_{n+1}^{T} is free (because p_{n+1}^{T} does not belong to Max′(T)). If |X|< max(T_{0}) + 1, one of the points of C_{n−1}^{T_{0}} is labeled with 𝔯 or 𝔤, so one of the points of C_{n−1}^{T} is labeled with ρ or γ. Assume now that p_{n+1}^{T} is not free, then one of the two points p_{n−1}^{T} and p_{n+1}^{T} is an element of B′(T) and the other is an element of R′(T), which by Definition 12 have labels β and ρ, and their insertions in Π_{0}(T) plot two points labeled with 𝔟′ and 𝔯′, which contradicts (i). So (i) implies (ii).

Let us prove that (ii) implies (i). Suppose that p_{n+1}^{T} is free. Recall that the set X = X_{T} has the cardinality max(T) by Remark 18, so if max(T) = max(T_{0}) + 1 then we indeed have (i). Suppose now that max(T) < max(T_{0}) + 1. In general, by Proposition 3, the roots of the points of C_{n−1}^{T} belong to {n − 1, n, n + 1, 2n}. Since p_{n+1}^{T} is free, these roots cannot be n + 1. Since max′(T) = omax(T_{0}) − max(T) ≥ 2, the point p_{n−1}^{T} cannot be located in the box (n − 1 : n − 1) (otherwise Max′(T) would be {p_{n−1}^{T}} because p_{n+1}^{T} is free, whereas its cardinality exceeds 2). Consequently, if the roots of the points of C_{n−1}^{T} are n − 1 and n, then the point p of C_{n−1}^{T} whose root is n − 1 is free, which implies that p is an element of G(T) (because the point whose root is n belongs to B(T)), and hence p is labeled with γ and its insertion in Π_{0}(T) plots a point labeled with 𝔤 in C_{n−1}^{T_{0}}. Otherwise, the roots of the points of C_{n−1}^{T} are n and 2n, in particular the point q of C_{n−1}^{T} whose root is 2n belongs to R(T), so q is labeled with ρ and its insertion in Π_{0}(T) plots a point labeled with 𝔯 in C_{n−1}^{T_{0}}. In both cases, we obtain (i).

The following lemma is a consequence of Lemma 21 and Lemma 22.

Lemma 23. Let T_{0} ∈ T_{n−1}^{e}, X ⊊ Omax(T_{0}) and T ∈ 𝔗(T_{0}, X). The following assertions are equivalent.

1. The set 𝔗(T_{0}, X) is defined in the situation S_{3} of Definition 17.

2. The point p_{n+1}^{T} is not free and one point of C_{n−1}^{T} is an element of R(T) or G(T).

3. The set X contains the last element p^{r} of R(T_{0}),|X|≤ max(T_{0}), and no two elements of Omax(T_{0})\X are labeled with 𝔟′ and 𝔯′.

Proposition 24. For all i ∈ [0, n − 2] and T_{0} ∈ T_{n−1,i}, the set Π^{−1}(T_{0}) ⊂ ⨆_{k=0}^{i+1} T_{n,k}^{e} is partitioned as follows:

• Π^{−1}(T_{0}) ∩ T_{n,0}^{e} has one single element, which has fr(T_{0}) free points;

• Π^{−1}(T_{0}) ∩ T_{n,i+1}^{e} has i + 2 elements, each of which has fr(T_{0}) + 1 free points;

• for all k ∈ [i], let N_{k}(T_{0}) be the number of elements T ∈ Π^{−1}(T_{0}) ∩ T_{n,k}^{e} such that p_{n+1}^{T} is free. All these tableaux have fr(T_{0}) + 1 free points. Afterwards, in addition to these tableaux, the set Π^{−1}(T_{0}) ∩ T_{n,k}^{e} is also composed of

– \binom{i+1}{k} tableaux whose (n−1)-th column contains no element of R(T) or G(T), each of which has fr(T_{0}) free points;

– 2 (\binom{i+1}{k−1} − N_{k}(T_{0})) other tableaux, each of which has fr(T_{0}) free points.

Proof. By Formula (8), the set Π^{−1}(T_{0}) ∩ T_{n,0}^{e} is 𝔗(T_{0}, ∅). By Lemma 21, the set 𝔗(T_{0}, ∅) is defined in the situation S_{1} of Definition 17. Hence 𝔗(T_{0}, ∅) has one single element T^{1} such that fr(T^{1}) = fr(T_{0}) in view of Remark 19.

Still by Formula (8), the set Π^{−1}(T_{0}) ∩ T_{n,i+1}^{e} is

⨆_{\begin{matrix}X⊂Omax(T_{0}), \\ |X|=i+1 \end{matrix}} 𝔗(T_{0}, X),

and for every of the \binom{i+2}{i+1} = i + 2 subsets X ⊂ Omax(T_{0}) whose cardinalities are i + 1, the set 𝔗(T_{0}, X) is defined in the situation S_{2} of Definition 17 in view of Lemma 22, so 𝔗(T_{0}, X) contains one single element T^{2} such that fr(T^{2}) = fr(T_{0}) + 1 in view of Remark 19.

Let k ∈ [i]. Consider the tableaux T ∈ Π^{−1}(T_{0}) ∩ T_{n,k}^{e} such that p_{n+1}^{T} is not free and no point of C_{n−1}^{T} is an element of R(T) or G(T). By Formula (8) and Lemma 21, the set of these tableaux is ⨆_{X} 𝔗(T_{0}, X) where the union is over the subsets X ⊂ Omax(T_{0})\{p^{r}} (where p^{r} is the last element of R(T_{0})) such that |X|= k. Since omax(T_{0}) = i + 2, there are \binom{i+1}{k} such subsets, and for every of these subsets X, the set 𝔗(T_{0}, X) is defined in the situation S_{1} of Definition 17, and hence 𝔗(T_{0}, ∅) has one single element T^{1} such that fr(T^{1}) = fr(T_{0}) in view of Remark 19.

Consider now the N_{k}(T_{0}) tableaux T ∈ Π^{−1}(T_{0}) ∩ T_{n,k}^{e} such that p_{n+1}^{T} is free. By Formula (8) and Lemma 22, the set of these tableaux is the union ⨆_{X} 𝔗(T_{0}, X) over the subsets X ⊂ Omax(T_{0}) such that p^{r} ∈ X, |X|= k and no two elements of Omax(T_{0})\X are labeled with 𝔟′ and 𝔯′. For every of these subsets X, the set 𝔗(T_{0}, X) is defined in the situation S_{2} of Definition 17, and hence 𝔗(T_{0}, X) has one single element T^{2} such that fr(T^{2}) = fr(T_{0}) + 1 in view of Remark 19. Consequently, the number of subsets X ⊂ Omax(T_{0}) that contain p^{r}, whose cardinality is k, and such that no two elements of Omax(T_{0})\X are labeled with 𝔟′ and 𝔯′, is exactly N_{k}(T_{0}).

Finally, consider the tableaux T ∈ Π^{−1}(T_{0}) ∩ T_{n,k}^{e} such that p_{n+1}^{T} is not free and one of the points of C_{n−1}^{T} is an element of R(T) or G(T). In view of the above paragraphs, they are exactly the tableaux T ∈ Π^{−1}(T_{0}) ∩ T_{n,k}^{e} defined in the situation S_{3} of Definition 17. By Lemma 23, the set of these tableaux is ⨆_{X} 𝔗(T_{0}, X) where the union is over the subsets X ⊂ Omax(T_{0}) such that p^{r} ∈ X, |X|= k, and there exist two elements of Omax(T_{0})\X labeled with 𝔟′ and 𝔯′. Since there exist \binom{i+1}{k−1} subsets X ⊂ Omax(T_{0}) that contain p^{r} and whose cardinality is k, in view of the previous paragraph, the number of these subsets X such that there exist two elements of Omax(T_{0})\X labeled with 𝔟′ and 𝔯′ is exactly \binom{i+1}{k−1}−N_{k}(T_{0}). For every of these subsets X, the set 𝔗(T_{0}, X) is defined in the situation S_{3} of Definition 17. Hence 𝔗(T_{0}, X) has two elements T^{3/} and T^{3\} such that fr(T^{3/}) = fr(T^{3\}) = fr(T_{0}) in view of Remark 19, so the total number of tableaux T ∈ Π^{−1}(T_{0}) ∩ T_{n,k}^{e} defined in the situation S_{3} is exactly 2 (\binom{i+1}{k−1} − N_{k}(T_{0})).

Corollary 25. The integers (e_{n,k})_{0≤k≤n−1} satisfy the recursive formulas (1), (2), and (3). This proves Theorem 7 in view of e_{1,0} = 1 = c_{1,0}.

Proof. Let n ≥ 2. By Proposition 20, we have T_{n,k}^{e} ⊂ ⨆_{i=k−1}^{n−2} Π^{−1}(T_{n−1,i}^{e}) for all k ∈ [n − 1],

and:

• For all i ∈ [0, n − 2], each tableau T_{0} ∈ T_{n−1}^{e} gives birth to one tableau T ∈ T_{n,0}^{e}, such that fr(T) = fr(T_{0}). Hence

e_{n,0} = ∑_{T_{0}∈T_{n−1}^{e}} 2^{fr(T_{0})−1} = ∑_{i=0}^{n−2} 2^{i}e_{n−1,i},

which is Formula (1).

• For all k ∈ [n − 2],

1. each tableau T_{0} ∈ T_{n−1,k−1}^{e} generates k + 1 tableaux T ∈ T_{n,k}^{e}, such that fr(T) = fr(T_{0}) + 1. Hence

∑_{\begin{matrix}T ∈T_{n,k}^{e}, \\ Π(T)∈T_{n−1,k−1}^{e} \end{matrix}} 2^{fr(T)−1−k} = (k + 1) ∑_{T_{0}∈T_{n−1,k−1}^{e}} 2^{fr(T_{0})−1−(k−1)}

= (k + 1)e_{n−1,k−1}; 2. for all i ∈ [k, n−2], each tableau T_{0} ∈ T_{n−1,i}^{e} gives birth to \binom{i+1}{k}+2 (\binom{i+1}{k−1} − N_{k}(T_{0})) tableaux T ∈ T_{n,k}^{e} such that fr(T) = fr(T_{0}), and N_{k}(T_{0}) tableaux T ∈ T_{n,k}^{e} such that fr(T) = fr(T_{0}) + 1. Hence the sum ∑_{\begin{matrix}T ∈T_{n,k}^{e}, \\ Π(T)∈T_{n−1,i}^{e} \end{matrix}} 2^{fr(T)−1−k} equals

∑_{T_{0} ∈T_{n−1,i}^{e}} (\binom{i + 1}{k}+2 (\binom{i + 1}{k − 1}−N_{k}(T_{0}))) 2^{fr(T_{0})−1−k} +N_{k}(T_{0})2^{fr(T_{0})−k}

= 2^{i−k} (\binom{i + 1}{k} + 2\binom{i + 1}{k − 1}) ∑_{T_{0}∈T_{n−1,i}^{e}} 2^{fr(T_{0})−1−i}

= 2^{i−k} (\binom{i + 1}{k} + 2\binom{i + 1}{k − 1}) e_{n−1,i}.

The equalities of (i) and (ii) give

∑_{T ∈T_{n,k}^{e}} 2^{fr(T)−1−k} = (k + 1)e_{n−1,k−1} + 2^{i−k} (\binom{i + 1}{k} + 2\binom{i + 1}{k − 1}) e_{n−1,i},

which is Formula (2).

• Finally note that Π(T_{n,n−1}^{e}) ⊂ T_{n−1,n−2}^{e}, and each tableau T_{0} ∈ T_{n−1,n−2}^{e} generates n tableaux T ∈ T_{n,n−1}^{e}, such that fr(T) = fr(T_{0}) + 1. Hence

e_{n,n−1} = ∑_{T ∈T_{n,n−1}^{e}} 2^{fr(T)−1−(n−1)} = n ∑_{T_{0}∈T_{n−1,k−1}^{e}} 2^{fr(T_{0})−1−(n−2)}
= ne_{n−1,n−2},

which is Formula (3).

This completes the proof.

4 Proof of Theorem 10

In this section, we construct a surjection P : T_{n}^{e} ↠ T_{n−1}^{o}(n ≥ 2) such that

∑_{T ∈P^{−1}(T_{0})} 2^{fr(T)−1−max(T)}x^{max(T)} = 2^{fr(T_{0})−g(T_{0})}x^{v(T_{0})}(1 + x)^{g(T_{0})}  (9)

for all T_{0} ∈ T_{n−1}^{o}, which proves Theorem 10 in view of Theorem 7.

Definition 26. Let T ∈ T_{n}^{e}. We label the elements of B(T) and R(T) with the letter ν, and the elements of G(T) with the letter γ.

Definition 27 (Map P : T_{n}^{e} → T_{n−1}^{o}). Let T ∈ T_{n}^{e}. We first define a tableau P_{0}(T), made

up of n − 1 columns and 2n − 1 rows, containing a point in its box (j : i^{≈}) for all points

p = (j : i) of T that does not belong to Max(T) (in particular j < n), where

i^{≈} = \begin{cases}i, & if i < n; \\ i − 1, & otherwise. \end{cases}

For example, for the tableau T_{1} ∈ T_{7}^{e} depicted in Figure 5, we obtain the tableau P_{0}(T_{1}) of Figure 17.

\begin{matrix}1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ 9 \\ 10 \\ 11 \\ 12 \\ 13 \\ 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ ⋆ \end{matrix}

Figure 17: The tableau P_{0}(T_{1}).

Afterwards, for j from 1 to n − 1, if C_{j}^{T} contains a point p labeled with ν (respectively γ), we insert a point in the box (j : 2n − 1) of P_{0}(T) (respectively the box (j : j)), following Definition 11.

Let P(T) be the tableau obtained at the end of this algorithm. It is straightforward by Definition 11 that P(T) is an element of T_{n−1}^{o}.

For example, for the tableau T = T_{1} ∈ T_{7}^{e} (see Figure 5), the tableau P(T_{1}) ∈ T_{6}^{o} is as depicted in Figure 10.

Let now T_{0} ∈ T_{n−1}^{o}. To construct P^{−1}(T_{0}), we consider four words b, r, br, bg with which we will label the columns of T_{0} that contain elements of V (T_{0}) (recall that if a point of a column C of T_{0} belongs to G(T_{0}), then the other point of C belongs to V (T_{0})). Let

J(T_{0}) = {j ∈ [n − 1] : C_{j}^{T_{0}} contains an element of V (T_{0})},
J_{g}(T_{0}) = {j ∈ [n − 1] : C_{j}^{T_{0}} contains an element of G(T_{0})}.

We have J_{g}(T_{0}) ⊂ J(T_{0}), |J(T_{0})|= v(T_{0}), |J_{g}(T_{0})|= g(T_{0}). Consider the set L(T_{0}) of the functions l : J(T_{0}) → {b, r, bg, br} such that l(j) ∈ {b, r} if j ∉ J_{g}(T_{0}), otherwise l(j) ∈ {br, bg, r}. The cardinality of L(T_{0}) is |L(T_{0})|= 2^{v(T_{0})−g(T_{0})}3^{g(T_{0})}.

Definition 28. For all l ∈ L(T_{0}), we define a tableau U^{l}(T_{0}) ∈ T_{n}^{e} as follows. First consider a tableau U_{0}^{l}(T_{0}) made up of n columns and 2n rows, that contains points in its boxes (j : \overline{\overline{i}})

for all points (j : i) of T_{0} that does not belong to V (T_{0}) or G(T_{0}), where \overline{\overline{i}} is defined as i if i < n, as i + 1 otherwise. Let us set T = U_{0}^{l}(T_{0}). For j from 1 to n − 1, assume that C_{j}^{T_{0}} contains an element of V (T_{0}) (otherwise C_{j}^{T} already contains two points and we do nothing).

• If no point of C_{j}^{T_{0}} belongs to G(T_{0}), we have j ∈ J(T_{0})\J_{g}(T_{0}), and l(j) ∈ {b, r}. If l(j) = b (respectively l(j) = r), then we insert a point in the box (j : n) (respectively (j : 2n)) of T.

• Otherwise j ∈ J_{g}(T_{0}) and l(j) ∈ {br, bg, r}. If l(j) = br (respectively bg, r), then we insert two points in the boxes (j : n) and (j : 2n) (respectively (j : n) and (j : j), (j : 2n) and (j : j)) of T.

At the end of the algorithm, we insert two points in the boxes (n : n) and (n : 2n) of T. By Definition 11, the tableau T has become an element of T_{n}^{e}, which we denote by U^{l}(T_{0}).

For example, the tableau T_{1} ∈ T_{7}^{e} depicted in Figure 5 is U^{l}(P(T_{1})), where recall that

P(T_{1}) ∈ T_{6}^{o} is the tableau depicted in Figure 10, and where l = (\begin{matrix}2 & 3 & 4 \\ bg & b & r \end{matrix}).

Proposition 29. The set P^{−1}(T_{0}) is exactly {U^{l}(T_{0}) : l ∈ L(T_{0})} (so P is surjective).

Proof. Let T ∈ P^{−1}(T_{0}). By Definition 27, for all j ∈ [n−1], we have j ∈ J(T_{0}) (respectively j ∈ J_{g}(T_{0})) if and only if one of the points of C_{j}^{T} belongs to Max(T) (respectively to G(T)). We then define l_{T} ∈ L(T_{0}) by

l_{T} (j) = \begin{cases}b, & if C_{j}^{T} has a point of B(T) and no point of R(T) or G(T); \\ br, & if C_{j}^{T} has a point of B(T) and a point of R(T); \\ bg, & if C_{j}^{T} has a point of B(T) and a point of G(T); \\ r, & if C_{j}^{T} has a point of R(T) and no point of B(T); \end{cases}

for all j ∈ J(T_{0}). It is easy to check that T = U^{l_{T}} (T_{0}), and that P(U^{l}(T_{0})) = T_{0} for all l ∈ L(T_{0}).

Proposition 30. Formula (9) is true.

Proof. Let l ∈ L(T_{0}) and T = U^{l}(T_{0}) ∈ P^{−1}(T_{0}). Let us determine fr(T) and max(T) in terms of T_{0} and l. First of all, note that in general all the elements of V (T_{0}) and G(T_{0}) are free points of T_{0}. Let fr_{0}(T_{0}) = fr(T_{0}) − v(T_{0}) − g(T_{0}). By Definition 28, fr_{0}(T_{0}) is the number of free points of T that were initially in U_{0}^{l}(T_{0}). Let δ_{l} ∈ [0, g(T_{0})] be the number of elements j ∈ J_{g}(T_{0}) such that l(j) = r. By construction of T, for all of these δ_{l} integers j, the two points of C_{j}^{T_{0}} are an element of V (T_{0}) and an element of G(T_{0}) whose insertions in U_{0}^{l}(T_{0}) plot two free points, the first of which belongs to R(T), the second of which does not belong to Max(T). Consequently, by Remark 6, we have

b(T) + r(T) = v(T_{0}),
g(T) = g(T_{0}) − δ_{l},
max(T) = b(T) + r(T) + g(T)
= v(T_{0}) + g(T_{0}) − δ_{l},
fr(T) = fr_{0}(T_{0}) + (max(T) + 1) + δ_{l}
= fr(T_{0}) + 1,

so that

2^{fr(T)−1−max(T)}x^{max(T)} = 2^{fr(T_{0})−v(T_{0})−g(T_{0})+δ_{l}}x^{v(T_{0})+g(T_{0})−δ_{l}}.  (10)

Now, for all δ ∈ [0, g(T_{0})], the number of elements l ∈ L(T_{0}) such that δ_{l} = δ equals \binom{g(T_{0})}{δ}2^{g(T_{0})−δ}2^{v(T_{0})−g(T_{0})} = \binom{g(T_{0})}{δ}2^{v(T_{0})−δ}, so, by Proposition 29 and Formula (10), the sum ∑_{T ∈P^{−1}(T_{0})} 2^{fr(T)−1−max(T)}x^{max(T)} equals

∑_{δ=0}^{g(T_{0})} \binom{g(T_{0})}{δ}2^{v(T_{0})−δ}2^{fr(T_{0})−v(T_{0})−g(T_{0})+δ}x^{v(T_{0})+g(T_{0})−δ}

= 2^{fr(T_{0})−g(T_{0})}x^{v(T_{0})+g(T_{0})} ∑_{δ=0}^{g(T_{0})} \binom{g(T_{0})}{δ}x^{−δ}

= 2^{fr(T_{0})−g(T_{0})}x^{v(T_{0})+g(T_{0})} (1 + \frac{1}{x})^{g(T_{0})} ,

hence Formula (9).

This proves Theorem 10.

5 Acknowledgment

The work of EF was partially supported by the grant RSF 19-11-00056.

References

[1] D. Barsky and D. Dumont, Congruences pour les nombres de Genocchi de 2e espèce, in Groupe de Travail d’Analyse Ultramétrique, Tome 7–8, 1979–1981, Exposé no. 34.

[2] A. Bigeni, Enumerating the symplectic Dellac configurations, preprint, 2017. Available

at http://arxiv.org/abs/1705.03804.

[3] A. Bigeni, A generalization of the Kreweras triangle through the universal sl_{2} weight system, J. Combin. Theory Ser. A 161 (2019), 309–326.

[4] A. Bigeni, Combinatorial interpretations of the Kreweras triangle in terms of subset tuples, Electron. J. Combin. 25 (2018), P4.44.

[5] A. Bigeni, Combinatorial study of the Dellac configurations and the q-extended normalized median Genocchi numbers, Electron. J. Combin. 21 (2014), P2.32.

[6] A. Bigeni and E. Feigin, Symmetric Dellac configurations and symplectic/orthogonal flag varieties, Linear Algebra Appl. 573 (2019), 54–79.

[7] G. Cerulli Irelli, M. Lanini, and P. Littelmann, Degenerate flag varieties and Schubert varieties: a characteristic free approach, Pacific J. Math 284 (2016), 283–308.

[8] G. Cerulli Irelli, E. Feigin, and M. Reineke, Quiver Grassmannians and degenerate flag varieties, Algebra Number Theory 6 (2012), 165–194.

[9] H. Dellac, Problem 1735, L’Intermédiaire des Mathématiciens 7 (1900), 9–10.

[10] D. Dumont, Interprétations combinatoires des nombres de Genocchi, Duke Math. J. 41 (1974), 305–318.

[11] D. Dumont and A. Randrianarivony, Dérangements et nombres de Genocchi, Discrete Math. 132 (1994), 37–49.

[12] D. Dumont and J. Zeng, Further results on Euler and Genocchi numbers, Aequationes Math. 47 (1994), 31–42.

[13] X. Fang and G. Fourier, Torus fixed points in Schubert varieties and normalized median Genocchi numbers, Sém. Lothar. Combin. 75 (2015), Art. B75f.

[14] E. Feigin, Degenerate flag varieties and the median Genocchi numbers, Math. Res. Lett. 18 (2011), 1163–1178.

[15] E. Feigin, The median Genocchi numbers, q-analogues and continued fractions, European J. Combin. 33 (2012), 1913–1918.

[16] E. Feigin, 𝔾_{a}^{M} degeneration of flag varieties, Selecta Math. 18 (2012), 513–537.

[17] E. Feigin, M. Finkelberg, and P. Littelmann, Symplectic degenerate flag varieties, Canad. J. Math. 66 (2014), 1250–1286.

[18] G. Han and J. Zeng, On a q-sequence that generalizes the median Genocchi numbers, Ann. Sci. Math. Québec 23 (1999), 63–72.

[19] G. Han and J. Zeng, q-Polynômes de Gandhi et statistique de Denert, Discrete Math. 205 (1999), 119–143.

[20] G. Kreweras, Sur les permutations comptées par les nombres de Genocchi de 1-ière et 2-ième espèce, European J. Combin. 18 (1997), 49–58.

[21] A. Randrianarivony and J. Zeng, Une famille de polynômes qui interpole plusieurs suites classiques de nombres, Adv. in Appl. Math. 17 (1996), 1–26.

[22] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, published electronically at https://oeis.org, 2019.

[23] J. Zeng and J. Zhou, A q-analog of the Seidel generation of Genocchi numbers, European J. Combin. 27 (2006), 364–381.

2010 Mathematics Subject Classification: Primary 05A15, Secondary 14M15. Keywords: Dellac configuration, median Euler number, flag variety.

(Concerned with sequences \underline{A000366}, \underline{A000657}, \underline{A002832}, \underline{A098278}, and \underline{A098279}.)

Received April 19 2019; revised versions received April 11 2020; April 14 2020. Published in Journal of Integer Sequences, April 15 2020.

Return to Journal of Integer Sequences home page.