Séminaire Lotharingien de Combinatoire 64 (2010), Article B64b

GENERALIZED DUMONT–FOATA POLYNOMIALS AND ALTERNATIVE TABLEAUX

MATTHIEU JOSUAT-VERGÈS

Abstract. Dumont and Foata introduced in 1976 a three-variable symmetric refinement of Genocchi numbers, which satisfies a simple recurrence relation. A six-variable generalization with many similar properties was later considered by Dumont. It generalizes a lot of known integer sequences, and its ordinary generating function can be expanded as a Jacobi continued fraction. We give here a new combinatorial interpretation of the six-variable polynomials in terms of the alternative tableaux introduced by Viennot. A powerful tool to enumerate alternative tableaux is the so-called “matrix Ansatz,” and using this we show that our combinatorial interpretation naturally leads to a new proof of the continued fraction expansion.

1. Introduction

The unsigned Genocchi numbers {G_{2n}}_{n≥1} can be defined through their generating function:

(1.1)  ∑_{n=1}^{∞} G_{2n} \frac{x^{2n}}{(2n)!} = x · tan (\frac{x}{2}) .

They are related with even Bernoulli numbers B_{2n} by G_{2n} = 2(4^{n} − 1)|B_{2n}|, and they have a wide range of combinatorial properties [4, 10, 12, 14]. In the context of previous work by Carlitz, Riordan and Stein, an extension of these integers was proposed by Dumont and Foata [5]. It is defined by the recurrence F_{1}(x, y, z) = 1 and

(1.2)  F_{n}(x, y, z) = (x + y)(x + z)F_{n−1}(x + 1, y, z) − x^{2}F_{n−1}(x, y, z).

They show that the polynomial F_{n} is symmetric in x, y, and z, with non-negative coefficients, and such that F_{n}(1, 1, 1) = G_{2n+2}. Another nice property is that the generating function ∑_{n=1}^{∞} F_{n}t^{n} can be expanded as a J-fraction (we will be more precise right below). Gessel and Zeng [7] showed that F_{n+1} is the nth moment of some orthogonal polynomials known as continuous dual Hahn polynomials, which are an important sequence in the Askey-Wilson hierarchy [8].

Partially supported by the grant ANR08-JCJC-0011.

A further generalization of Genocchi numbers with many similar properties was defined by Dumont in terms of some combinatorial objects called escaliers [4]. It is a sequence of six-variable polynomials Γ_{n}(x, y, z, x̄, ȳ, z̄), or just Γ_{n} for short. They can be characterized by a recurrence relation which generalizes (1.2), and has been obtained independently by Randrianarivony [10] and Zeng [14]. For brevity, let Γ_{n}^{+} denote Γ_{n}(x + 1, y, z, x̄ + 1, ȳ, z̄).

Definition 1.1. The generalized Dumont–Foata polynomials are defined by Γ_{1} = 1 and

(1.3)  Γ_{n} = (x + z̄)(y + x̄)Γ_{n−1}^{+} + (x(ȳ − y) + x̄(z − z̄) − xx̄)Γ_{n−1}.

Quite a lot of known integer sequences appear as specializations of Γ_{n} [10, 11, 14]: Genocchi numbers, median Genocchi numbers, Euler numbers, median Euler numbers, Springer numbers. The polynomial Γ_{n} generalizes F_{n} since we have Γ_{n}(x, y, z, x, y, z) = F_{n}(x, y, z).

Dumont [4] conjectured that we have the following J-fraction for ∑ Γ_{n}t^{n}:

(1.4)  ∑_{n=1}^{∞} Γ_{n}t^{n} = \frac{t}{1 − b_{0}t − \frac{λ_{1}t^{2}}{1 − b_{1}t − \frac{λ_{2}t^{2}}{...}}} ,

where the parameters b_{n} and λ_{n} are defined by:

\begin{aligned}b_{n} & = (x + n)(ȳ + n) + (y + n)(z̄ + n) + (z + n)(x̄ + n) − n(n + 1), \\ λ_{n} & = n(x̄ + y + n − 1)(ȳ + z + n − 1)(z̄ + x + n − 1). \end{aligned} ; (1.5)

This was proved independently by Randrianarivony [10] and Zeng [14] (and of course this implies the J-fraction expansion for ∑ F_{n}t^{n}). More precisely, Randrianarivony’s method consists in the study of a Stieltjes tableau and Zeng’s method consists in calculations of Hankel determinants.

The main goal of this article is to give a new combinatorial interpretation of Γ_{n} in terms of alternative tableaux [9, 13] and six statistics on them, and obtain as a consequence a new proof of the continued fraction expansion (1.4). Alternative tableaux were introduced by Viennot [13] in the context of a model of statistical physics called Partially Asymmetric Simple Exclusion Process (PASEP) and previous work of Corteel and Williams [2]. The “matrix Ansatz” first appeared in [3], as a way to obtain the stationary distribution of the PASEP. In the combinatorial context, it is a method to enumerate these alternative tableaux in terms of operators satisfying certain relations. We will also describe an analog of the matrix Ansatz to enumerate escaliers, which are the combinatorial objects used by Dumont to define Γ_{n} in [4].

This article is organized as follows. In Section 2 we give definitions and known facts about alternative tableaux and the matrix Ansatz. In Section 3 we prove the new combinatorial interpretation of Γ_{n} in terms of alternative tableaux using the recurrence (1.3). Section 4 contains our new proof of the continued fraction expansion (1.4). In Section 5, we describe the analog of the matrix Ansatz to enumerate escaliers.

2. Alternative tableaux

Throughout this article we use the French convention for Young diagrams, and Young diagrams may contain rows or columns of size 0. Any Young diagram is characterized by its upper-right boundary, which is a sequence of unit steps going left or going down. We will encode this sequence by a word in the two letters D and E, so that D corresponds to the step → and E corresponds to the step ↓. For example, DDEDE is the Young diagram with two rows of respective lengths 2 and 3.

Definition 2.1. Let λ be a Young diagram. An alternative tableau of shape λ is a filling of λ such that each cell is either empty, contains an arrow ← or an arrow ↓, and each arrow has a clear view to the boundary. More precisely, all cells below a ↓ in the same column (or to the left of a ← in the same row) are empty. A column (respectively row) of an alternative tableau is free if it contains no ↓ (respectively no ←). We denote by fr(T) (respectively fc(T)) the number of free rows (respectively free columns) of T. See Figure 1 for examples. We use here the notation with arrows as introduced by Nadeau [9].

↓ ↓ ←  ^{← ← ← ↓ ↓}  ^{← ← ← ↓}  ^{←← ← ↓ ↓}

Figure 1. Examples of alternative tableaux.

Alternative tableaux of a given shape can be enumerated via a method called matrix Ansatz. This method appeared in the context of a model of statistical physics (the partially asymmetric simple exclusion process), where it is used to derive the stationary probabilities of any state of the process.

Proposition 2.2 (Corteel, Williams [2]). Let ⟨W | be a row vector, |V ⟩ a column vector, and D and E matrices such that: (2.1)

⟨W |V ⟩ = 1, ⟨W |E = x̄⟨W |, D|V ⟩ = y|V ⟩, and DE − ED = D + E.

Let w be a word in the two letters D and E, then we have

(2.2)  ⟨W |w|V ⟩ = ∑_{T} x̄^{fr(T)}y^{fc(T)}

where the sum is over alternative tableaux T of shape w.

The result of Corteel and Williams was actually stated in terms of permutation tableaux, which are slightly different objects. The above — equivalent — statement in terms of alternative tableaux can be found in Viennot [13] and Nadeau [9], as well as the bijection between permutation tableaux and alternative tableaux. We have chosen to use alternative tableaux in this work because of their symmetry. Indeed, there is an elementary involution on alternative tableaux which is conjugation. To conjugate a tableau, take the reflection of the whole picture with respect to the South-West to North-East axis symmetry (in particular, the ← and ↓ are exchanged). See [9] for details.

Note that relations (2.1) ensure that ⟨W |w|V ⟩ is well-defined and can be computed explicitly. Indeed, we can use DE − ED = D + E to obtain some coefficients c_{i,j} such that w = ∑_{i,j} c_{i,j}E^{i}D^{j}, and from the other relations we can obtain ⟨W |w|V ⟩. We refer to [2, 1] for more details.

Although not necessary to compute ⟨W |w|V ⟩ for a given word w, it is useful to have explicit matrices satisfying the PASEP matrix Ansatz. It can be checked [3] that the following ℕ × ℕ-matrices: (2.3)

D = (\begin{matrix}y & 1 & & & (0) \\ & y + 1 & 2 \\ & & y + 2 & 3 \\ & & & y + 3 & ... \\ (0) & & & & ... \end{matrix} ) , E = (\begin{matrix}x̄ & & & & (0) \\ y + x̄ & x̄ + 1 \\ & y + x̄ + 1 & x̄ + 2 \\ & & y + x̄ + 2 & x̄ + 3 \\ (0) & & & ... & ... \end{matrix}) ,

satisfy DE − ED = D + E. They are essentially a particular case of matrices defined by Derrida et al. [3] in the context of the PASEP. As for the vectors, we can take ⟨W | = (1, 0, 0, …) and |V ⟩ = (1, 0, 0, …)^{∗}, and all relations in (2.1) are satisfied.

3. The new combinatorial interpretation of Γ_{n}

It is known [13] that G_{2n+2} is the number of alternative tableaux whose shape is the staircase with n rows and columns, i.e., the Young diagram corresponding to the word (DE)^{n}. In [1], we have given three statistics on staircase alternative tableaux to give a combinatorial interpretation of F_{n}(x, y, z). These are: the number of free rows, the number of free columns, and the number of corners containing ← or ↓. Here, we give six statistics for the more general case of Γ_{n}. Another difference is that, in [1], the combinatorial interpretation was derived from the J-fraction for ∑ F_{n}t^{n}, but here we use the recurrence relation (1.3) to prove the result.

Definition 3.1. A column (respectively row) of an alternative tableau is empty if it contains no ↓ nor ←. Let T be an alternative tableau. We denote by:

• emr(T), the number of empty rows in T,

• fnc(T), the number of free non-empty columns in T,

• dco(T), the number of corners containing a ↓ in T,

• fnr(T), the number of free non-empty rows in T,

• emc(T), the number of empty columns in T,

• lco(T), the number of corners containing a ← in T.

Moreover, let T_{n} be the set of alternative tableaux whose shape is the staircase Young diagram with n rows and n columns.

For example, the rightmost tableau in Figure 1 is in T_{5}, and the six statistics that we have just defined are 2, 2, 2, 0, 1, 0, respectively. The main new result of this article is the following.

Theorem 3.2. For any n ≥ 1, we have

(3.1)  Γ_{n}(x, y, z, x̄, ȳ, z̄) = ∑_{T ∈T_{n−1}} x^{emr(T)}y^{fnc(T)}z^{dco(T)}x̄^{fnr(T)}ȳ^{emc(T)}z̄^{lco(T)}.

Proof. Both sides are equal to 1 when n = 1, so it suffices to show that the righthand side satisfies the recurrence relation (1.3). We distinguish six kinds of tableaux in the set T_{n−1}, according to the content of their leftmost column and upper left corner. Assuming that the theorem is true for n − 1, we will show that these six kinds of tableaux have generating functions which add up to the right-hand side of (1.3). This is summarized in the following table.

The leftmost column is:

The upper left corner contains:

↓  ←  nothing
empty  ×  ×  Case 4
xȳΓ_{n−1}

free non-empty

×

Case 2 Case 5

yz̄Γ_{n−1}^{+}  xy(Γ_{n−1}^{+} − Γ_{n−1})
non-free  Case 1  Case 3  Case 6
x̄zΓ_{n−1}  x̄z̄(Γ_{n−1}^{+} − Γ_{n−1}) xx̄(Γ_{n−1}^{+} − Γ_{n−1})

For example we will show that the tableaux of the fourth kind (case 4), i.e., those having an empty leftmost column, have generating function xȳΓ_{n−1}. The three cells containing a × in this table do not correspond to any tableaux.

← ← ↓ ↓ ↓  ^{← ← ↓ ↓ ←}  ^{← ← ↓ ↓}  ^{← ← ↓ ↓}

Figure 2. Recursive construction of staircase alternative tableaux.

• Case 1. When the upper-left corner contains a ↓, there is no other arrow in the leftmost column. This corresponds to the first picture in Figure 2. In this first kind of tableaux, the topmost row is free non-empty, and the upper left corner contains a ↓, so this gives a factor x̄z. After removing the leftmost column, there can remain any tableau in T_{n−2}, hence the factor Γ_{n−1}. So the first kind of tableaux gives indeed the term x̄zΓ_{n−1}.

• Case 2. There is a factor yz̄ since we assume that there is a ← in the upper left corner, and that the leftmost column is free and non-empty. These tableaux can be obtained the following way: consider any tableau T in T_{n−2}, add a column to its left with a ← in the topmost cell of the added column. We color some of the other cells in the added column in gray as in the second picture in Figure 2, such that a cell is colored if there is no ← to its right. Then, decide whether each gray cell is empty or contains a ←. All tableaux of the second kind can be obtained in this way, and the gray cells are in correspondence with the free rows of T. At the level of generating functions, this amounts to substituting x by x + 1 and x̄ by x̄ + 1. Indeed, an empty (respectively free non-empty) row remains so if we add nothing in the gray cell, but becomes non-free if we add a ←.

• Case 3. This corresponds to the second picture in Figure 2, but with the assumption that there is a ↓ in one of the gray cells. Let us consider the set S of tableaux of the second kind such that there is at least a ← in some gray cell. This set has generating function yz̄(Γ_{n−1}^{+} − Γ_{n−1}); indeed, we have already yz̄Γ_{n−1}^{+} for all the tableaux of the second kind, and the term −yz̄Γ_{n−1} removes the cases where all gray cells are empty. Then there is a bijection between this set S and the tableaux of the third kind. Indeed, let T ∈ S, consider the bottommost ← in the leftmost column of T, and replace this ← by a ↓. In this way, we obtain exactly the tableaux of the third kind. Replacing the ← by ↓ gives a factor x̄y^{−1} at the level of generating functions. Thus we obtain x̄z̄(Γ_{n−1}^{+} − Γ_{n−1}) for the third kind of tableaux.

• Case 4. This is similar to case 1, and it corresponds to the third picture in Figure 2. Here, removing the first column gives a factor xȳ since we assume that the leftmost column is empty, and hence the upper row is empty. There can remain any tableau in T_{n−2}, hence the factor Γ_{n−1}. Thus we obtain xȳΓ_{n−1} for the fourth kind of tableaux.

• Case 5. This corresponds to the fourth picture in Figure 2, with the assumption that the gray cells contain no ↓ and at least a ←. Here the gray cells are obtained exactly as in case 2 above. Proceeding similar to case 3 above, we obtain xy(Γ_{n−1}^{+} − Γ_{n−1}) for the fifth kind of tableaux.

• Case 6. There is a bijection between the fifth kind and the sixth kind of tableaux, similar to the bijection used in case 3. From a tableau of the fifth kind, consider the bottommost ← in the leftmost column, and replace it by a ↓. Replacing the ← by ↓ gives a factor x̄y^{−1} at the level of generating functions. Thus we obtain xx̄(Γ_{n−1}^{+} − Γ_{n−1}) for the sixth kind of tableaux.

Adding the six terms in the above table, we get the right-hand side of (1.3). This shows that the right-hand side of (3.1) satisfies the same recurrence as Γ_{n} and completes the proof. □

As previously mentioned, there is a simple bijection between alternative tableaux and permutation tableaux, and it is possible to derive a combinatorial interpretation of Γ_{n} in terms of permutation tableaux, but the result is much more natural with the alternative tableaux. In particular, the conjugation of alternative tableaux provides an easy way to prove a symmetry property of Γ_{n}, which has been first given by Randrianarivony [10] and Zeng [14].

Proposition 3.3 ([10, 14]). For any permutation σ = u, v, w of x, y, z we have: • if σ has positive sign, then Γ_{n}(u, v, w, ū, v̄, w̄) = Γ_{n}(x, y, z, x̄, ȳ, z̄),

• if σ has negative sign, then Γ_{n}(u, v, w, ū, v̄, w̄) = Γ_{n}(x̄, ȳ, z̄, x, y, z). In particular, F_{n}(x, y, z) = Γ_{n}(x, y, z, x, y, z) is symmetric in x, y, and z.

Proof. From the recurrence relation (1.3), we have

(3.2)  Γ(x, y, z, x̄, ȳ, z̄) = Γ(x̄, z̄, ȳ, x, z, y).

From the combinatorial interpretation in (3.1) and using the conjugation of alternative tableaux, we have

(3.3)  Γ(x, y, z, x̄, ȳ, z̄) = Γ(ȳ, x̄, z̄, y, x, z).

All symmetries given in the statement of the proposition can be obtained by combining (3.2) and (3.3). □

It is rather curious that one symmetry is obvious from the combinatorial interpretation, and the other from the recurrence relation. In the model in terms of escaliers (see Section 5), only one symmetry is obvious, and this both from the combinatorial interpretation and the recurrence relation. Note that any symmetry of a generating function necessarily appears in the coefficients of its expansion as a J-fraction, and indeed it is straightforward to check that the coefficients b_{n} and λ_{n} defined in (1.5) have the same symmetries as Γ_{n}.

4. The continued fraction expansion

In this section, we show that Γ_{n} can be calculated via the matrix Ansatz, and we derive as a consequence a new proof of the continued fraction expansion for ∑ Γ_{n}t^{n}. We consider the matrix

(4.1)  M = ED + (z̄ + x − x̄)D + (z + ȳ − y)E + (ȳ − y)(x − x̄)I,

where D, E are defined in (2.3), and I is the identity matrix. It turns out that we can exploit Proposition 2.2 to obtain the following matrix representation of our polynomials Γ_{n+1}.

Proposition 4.1. For any n ≥ 0, we have

(4.2)  Γ_{n+1}(x, y, z, x̄, ȳ, z̄) = ⟨W |M^{n}|V ⟩.

To prove this, we need a few helpful definitions and lemmas.

Definition 4.2. Let T_{n}^{∗} be the set of pairs (T, X), where T ∈ T_{n} and X is a subset of the empty rows and columns of T. Such a pair (T, X) is called an extended tableau, and it will be represented the following way: from a picture of T, each row or column in X is distinguished by a dashed line going through it. See Figure 3 for some examples. Given U = (T, X) ∈ T_{n}^{∗}, we define

• hr(U) as the number of dashed rows,

• hc(U) as the number of dashed columns. For any statistic “stat” on alternative tableaux and U = (T, X) ∈ T_{n}^{∗}, we define stat(U) = stat(T). For any extended tableau U, we define the weight w(U) as

w(U) = x̄^{emr(U)−hr(U)}y^{fnc(U)}z^{dco(U)}x̄^{fnr(U)}y^{emc(U)−hc(U)}z̄^{lco(U)}(x − x̄)^{hr(U)}(ȳ − y)^{hc(U)}
= y^{fc(U)−hc(U)}z^{dco(U)}x̄^{fr(U)−hr(U)}z̄^{lco(U)}(x − x̄)^{hr(U)}(ȳ − y)^{hc(U)},

(4.3)

the last equality following from emr(T) + fnr(T) = fr(T) and emc(T) + fnc(T) = fc(T) for any alternative tableau T.

← ← ↓ ↓  ^{←← ↓  ↓}

Figure 3. Example of two extended alternative tableaux.

Lemma 4.3. We have:

(4.4)  ∑_{U∈T_{n}^{∗}} w(U) = ∑_{T ∈T_{n}} x^{emr(T)}y^{fnc(T)}z^{dco(T)}x̄^{fnr(T)}ȳ^{emc(T)}z̄^{lco(T)}.

Proof. In the sum ∑_{U∈T_{n}^{∗}} w(U), we have distinguished two kinds of empty rows (dashed or non-dashed) with respective weights x − x̄ and x̄ instead of one kind of empty row with weight x. Similarly we have distinguished two kinds of empty columns (dashed or non-dashed) with respective weights ȳ− y and y instead of one kind of empty column with weight ȳ. By an elementary argument, it is clear that these distinctions do not change the generating function. □

Definition 4.4. Let (T, X) be an extended tableau in T_{n}^{∗}. The profile of (T, X) is the sequence (i_{1}, …, i_{n}), where:

• i_{k} = 1 if the kth corner of T is empty,

• i_{k} = 2 if the kth corner of T contains a ←,

• i_{k} = 3 if the kth corner of T is in a dashed row but not in a dashed column,

• i_{k} = 4 if the kth corner of T contains a ↓,

• i_{k} = 5 if the kth corner of T is in a dashed column but not in a dashed row,

• i_{k} = 6 if the kth corner of T is in a dashed column and in a dashed row. Here the corners are numbered from the upper left to the lower right. For example, the first extended tableau in Figure 3 has profile (1, 5, 1, 4, 6), and the second one has profile (5, 2, 3, 1, 4).

Lemma 4.5. Let M_{1}, …, M_{6} be the matrices

(4.5)  \begin{matrix}M_{1} = ED, & M_{2} = z̄D, & M_{3} = (x − x̄)D, \\ M_{4} = zE, & M_{5} = (ȳ − y)E, & M_{6} = (ȳ − y)(x − x̄)I. \end{matrix}

For any (i_{1}, …, i_{n}) ∈ {1, …, 6}^{n}, we have

(4.6)  ∑_{U} w(U) = ⟨W |M_{i_{1}} ⋯ M_{i_{n}}|V ⟩,

where the sum is over extended tableaux U of profile (i_{1}, …, i_{n}).

Proof. Let w be the word obtained from i_{1} … i_{n} through the substitution 1 ↦ ED, 2 ↦ D, 3 ↦ D, 4 ↦ E, 5 ↦ E, 6 ↦ ϵ (ϵ being the empty word). The main point is that there is a bijection ϕ between elements in T_{n}^{∗} of profile (i_{1}, …, i_{n}) and alternative tableaux of shape w. Indeed, to build an extended tableau, once the contents of the corners are specified, it remains only to choose an alternative tableau of a smaller shape. More precisely, the bijection can be constructed in the following way:

• for each empty corner of the extended tableau, remove the corresponding cell in the Young diagram,

• shrink each dashed row or column, • for each corner of the extended tableau containing a ← (respectively ↓), shrink the row (respectively column) containing it.

See Figure 4 for an example, where we give the image of the two extended tableaux in Figure 3.

← ← ↓  \overleftarrow{↓}

Figure 4. Images of extended tableaux by the map ϕ.

The weight of an extended tableau U of profile (i_{1}, …, i_{n}) is the product

y^{a}z^{b}x̄^{c}z̄^{d}(x − x̄)^{e}(ȳ − y)^{f},

where:

• a is the number of non-dashed free columns in U,

• b = dco(U) is the number of 4’s in (i_{1}, …, i_{n}),

• c is the number of non-dashed free rows in U,

• d = lco(U) is the number of 2’s in (i_{1}, …, i_{n}),

• e = hr(U) is the number of 3’s plus the number of 6’s in (i_{1}, …, i_{n}),

• f = hc(U) is the number of 5’s plus the number of 6’s in (i_{1}, …, i_{n}). An important property of the bijection ϕ is that the free rows (respectively columns) of ϕ(U) are in correspondence with non-dashed free rows (respectively columns) of U. It follows that

(4.7)  ∑_{U} w(U) = z^{b}z̄^{d}(x − x̄)^{e}(ȳ − y)^{f} ∑_{T} x̄^{fr(T)}y^{fc(T)},

where the first sum is over extended tableau of profile (i_{1}, …, i_{n}) and the second is over alternative tableau of shape w.

Now, examine the product M_{i_{1}} ⋯ M_{i_{n}}. The factors D and E in this product readily give the word w, and the other factors readily give z^{b}z̄^{d}(x − x̄)^{e}(ȳ − y)^{f}, so:

(4.8)  ⟨W |M_{i_{1}} ⋯ M_{i_{n}}|V ⟩ = z^{b}z̄^{d}(x − x̄)^{e}(ȳ − y)^{f}⟨W |w|V ⟩.

Using Proposition 2.2, the result follows from (4.7) and (4.8). □

Now we can prove Proposition 4.1.

Proof. Since M = ∑_{i=1}^{6} M_{i}, the expansion of M^{n} is also the sum of all products M_{i_{1}} ⋯ M_{i_{n}}, where (i_{1}, …, i_{n}) runs through the set {1, …, 6}^{n}. Hence,

(4.9)  ⟨W |M^{n}|V ⟩ = ∑_{(i_{1},...,i_{n})∈{1,...,6}^{n}}⟨W |M_{i_{1}} ⋯ M_{i_{n}}|V ⟩.

GENERALIZED DUMONT–FOATA POLYNOMIALS AND ALTERNATIVE TABLEAUX 11

Using Equation (4.6) in Lemma 4.5, this gives

(4.10)  ⟨W |M^{n}|V ⟩ = ∑_{U∈T_{n−1}^{∗}} w(U).

Using Equation (4.4) in Lemma 4.3 and Theorem 3.2, this is equal to Γ_{n+1}. □

From the definitions of D and E in (2.3), the matrix M defined in (4.1) can be calculated explicitly, and we obtain the following result.

Proposition 4.6. The matrix M = (M_{i,j})_{i,j∈ℕ} is tridiagonal, and for any i ≥ 0 we have

(4.11)  M_{i,i} = b_{i} and M_{i,i+1}M_{i+1,i} = λ_{i+1},

where b_{i} and λ_{i} are defined in (1.5).

Proof. We have

M_{i,i} = E_{i,i}D_{i,i} + E_{i,i−1}D_{i−1,i} + (z̄ + x − x̄)D_{i,i} + (z + ȳ − y)E_{i,i} + (ȳ − y)(x − x̄)
= (x̄ + i)(y + i) + (y + x̄ + i − 1)i + (z̄ + x − x̄)(y + i)
+ (z + ȳ − y)(x̄ + i) + (ȳ − y)(x − x̄)
= xȳ + yz̄ + zx̄ + i(x̄ + ȳ + z̄ + x + y + z) + i(2i − 1) = b_{i}.

We have also

M_{i,i+1} = E_{i,i}D_{i,i+1} + (z̄ + x − x̄)D_{i,i+1}
= (x̄ + i)(i + 1) + (z̄ + x − x̄)(i + 1) = (x + z̄ + i)(i + 1),

and

M_{i+1,i} = E_{i+1,i}D_{i,i} + (z + ȳ − y)E_{i+1,i} = (y + x̄ + i)(y + i) + (z + ȳ − y)(y + x̄ + i)
= (x̄ + y + i)(z + ȳ + i).

Hence, M_{i,i+1}M_{i+1,i} = λ_{i+1}. It is straightforward to check that the other coefficients in M are 0, and this completes the proof. □

As a direct consequence of Propositions 4.1 and 4.6, let us give a new proof of the continued fraction expansion given in (1.4). First, note that ⟨W |M^{n}|V ⟩ is the top-left coefficient (M^{n})_{0,0} of the matrix M^{n}. This coefficient can be obtained by expanding the product M^{n}, and we obtain

(4.12)  ⟨W |M^{n}|V ⟩ = ∑_{i_{1},...,i_{n−1}≥0} M_{0,i_{1}}M_{i_{1},i_{2}} ⋯ M_{i_{n−2},i_{n−1}}M_{i_{n−1},0}.

Since the matrix M is tridiagonal, we can restrict the sum to the case where two successive indices differ by at most 1, i.e., |i_{j} − i_{j+1}| ≤ 1 for any j ∈ {0, …, n − 1}, where i_{0} = i_{n} = 0. These indices thus define the successive heights of a Motzkin path. Then (4.12) shows that Γ_{n+1} can be seen as the generating function of Motzkin paths of n steps, with a weight b_{i} for a level step at height i, and a weight λ_{i} for a step ↗ between height i − 1 and i. By a standard argument [6] this implies the continued fraction given in (1.4).

5. The matrix Ansatz for escaliers

In the previous section, we have applied the link between alternative tableaux and matrices D and E satisfying DE − ED = D + E to obtain the continued fraction. In this section, we consider escaliers, which are the combinatorial objects used by Dumont [4] to define Γ_{n}. We will show that these objects can be enumerated by a similar method, but with matrices B and A satisfying BA − AB = A + I.

We will denote a Young diagram by a word in B and A in the same way as we did with D and E (B and A, respectively, correspond to steps → and ↓ along the North-East boundary of the Young diagram).

Definition 5.1. A surjective pretableau is a partial filling of a Young diagram with ×’s, such that there is at least one × in each row and at most one × in each column. A surjective tableau is a surjective pretableau such that there is exactly one × in each column. An escalier (of size n) is a surjective tableau of shape (BBA)^{n}. See Figure 5 for some examples.

× × × × ×  ^{× × × × × ×}

Figure 5. Examples of surjective pretableaux of shape (BBA)^{4}.

The definition of Γ_{n} by Dumont [4] is given in terms of escaliers of size n and six statistics on them. There is an obvious bijection between escaliers of size n and surjective pretableau of shape (BBA)^{n−1} (remove the bottom row of the escalier), so that Dumont’s definition is equivalent to the following (as mentioned in the introduction, this is also known to be equivalent with Definition 1.1).

Definition 5.2. A co-corner of the Young diagram (BBA)^{n} is a cell which is the left neighbor of a corner (for example the upper-left cell is a co-corner). Let S_{n} be the set of surjective pretableau of shape (BBA)^{n}. A column is empty if it contains no ×. A × is doubled if there is another × in the same row. We denote by:

• mi(T), the number of empty columns of odd index,

• fd(T), the number of corners containing a doubled ×,

• snd(T), the number of co-corners containing a non-doubled ×,

• mp(T), the number of empty columns of even index,

• fnd(T), the number of corners containing a non-doubled ×,

• sd(T), the number of co-corners containing a doubled ×, Finally, Γ_{n} can be defined as

(5.1)  Γ_{n} = ∑_{T ∈S_{n−1}} x^{mi(T)}y^{fd(T)}z^{snd(T)}x̄^{mp(T)}ȳ^{fnd(T)}z̄^{sd(T)}.

For example, the values of the six statistics on the first surjective pretableau in Figure 5 are 1, 1, 1, 2, 1, and 0. As for the second one, the values are 0, 1, 2, 2, 0, and 1. The fact that these objects also follow the recurrence (1.3) is seen by distinguishing several kinds of elements in S_{n−1} according to the content of the bottom row [10, 14].

The analog of the matrix Ansatz for escaliers is given in the following proposition. The proof is similar to the case of alternative tableaux, and various examples of this kind of results were given in [1].

Proposition 5.3. Let ⟨W | be a row vector, |V ⟩ a column vector, and A and B matrices such that:

(5.2)  ⟨W |V ⟩ = 1, ⟨W |A = 0, B|V ⟩ = 0, BA − AB = A + I.

Let w be a word in the two letters B and A. Then the number of surjective tableaux of shape w is ⟨W |w|V ⟩.

Proof. This is done by an induction on the number of cells in the Young diagram. If there is no cell, then w = A^{i}B^{j} for some i and j, so ⟨W |w|V ⟩ equals 0 if i > 0 or j > 0 and 1 otherwise. Since there is at least a × in each row and column of a surjective tableau, there is no such tableau of shape A^{i}B^{j} if i > 0 or j > 0, but we do have the “empty” surjective tableau in the “empty Young diagram” when i = j = 0.

Next, consider a word w which is not in the form A^{i}B^{j}. This means that we can factorize it into w = w_{1}BAw_{2}, and the factor BA corresponds to a corner of the Young diagram. We can distinguish three kinds of surjective tableaux of shape w, depending on the content of this corner.

• If the corner is empty, we can remove it and obtain any surjective tableaux of shape w_{1}ABw_{2}. By the induction hypothesis, their number is ⟨W |w_{1}ABw_{2}|V ⟩.

• If the corner contains a doubled ×, we can delete the corner and its column, and obtain any surjective tableau of shape w_{1}Aw_{2}. Their number is ⟨W |w_{1}Aw_{2}|V ⟩.

• If the corner contains a non-doubled ×, we can remove the corner and its row and column, and obtain any surjective tableau of shape w_{1}w_{2}. Their number is ⟨W |w_{1}w_{2}|V ⟩.

It follows that the number of surjective tableaux of shape w is

⟨W |w_{1}ABw_{2}|V ⟩ + ⟨W |w_{1}Aw_{2}|V ⟩ + ⟨W |w_{1}w_{2}|V ⟩ = ⟨W |w_{1}BAw_{2}|V ⟩ = ⟨W |w|V ⟩,

and this completes the induction step. □

It is easily checked that the ℕ × ℕ-matrices

(5.3)  B = (\begin{matrix}0 & 1 & & & (0) \\ & 1 & 2 \\ & & 2 & 3 \\ & & & 3 & ... \\ (0) & & & & ... \end{matrix}) ,  A = (\begin{matrix}0 & & & & (0) \\ 1 & 0 \\ & 1 & 0 \\ & & 1 & 0 \\ (0) & & & ... & ... \end{matrix}) ,

satisfy BA−AB = A+I. We keep the definition of ⟨W | and |V ⟩ as in the previous sections, since this also ensures that we have ⟨W |A = 0 and B|V ⟩ = 0.

To see how to use this result in the case of Γ_{n}, let us begin with the particular case y = z = ȳ = z̄ = 1. We know that the number of surjective tableaux of shape (BBA)^{n} is ⟨W |(BBA)^{n}|V ⟩. If we want to count surjective pretableaux, we have to authorize empty columns, and this is done by replacing B by B + I. Indeed, in the expansion of the product ⟨W |((B + I)(B + I)A)^{n}|V ⟩, the choice of B or I in some factor corresponds to the choice of leaving a column empty or not. So the number of surjective pretableaux of shape (BBA)^{n} is ⟨W |((B+I)(B+I)A)^{n}|V ⟩. If we want to follow the empty columns of odd (respectively even) index by the parameter x (respectively x̄), it suffices to mark the terms I, and we obtain Γ_{n+1}(x, 1, 1, x̄, 1, 1) = ⟨W |((B + xI)(B + x̄I)A)^{n}|V ⟩.

As for the general case, in the same way that we have obtained Proposition 4.1 from the combinatorial interpretation in terms of alternative tableaux, we can obtain the following from the combinatorial interpretation in terms of escaliers.

Proposition 5.4. For any n ≥ 0, we have Γ_{n+1} = ⟨W |N^{n}|V ⟩ where N is the matrix

(5.4) N = A(B +xI)(B +x̄I)+yz̄(A+I)+(zI +z̄A)(B +x̄I)+(ȳI +yA)(B +xI).

As in the previous section, we need some helpful definitions and lemmas.

Definition 5.5. The profile of T ∈ S_{n} is the sequence (i_{1}, …, i_{n}), where

• i_{k} = 1 if the kth co-corner and kth corner are empty,

• i_{k} = 2 if the kth co-corner and kth corner both contain a ×,

• i_{k} = 3 if the kth co-corner contains a non-doubled ×,

• i_{k} = 4 if the kth co-corner contains a doubled × and the kth corner is empty,

• i_{k} = 5 if the kth corner contains a non-doubled ×,

• i_{k} = 6 if the kth corner contains a doubled × and the kth co-corner is empty.

For example, the two surjective pretableaux in Figure 5 have profiles (5, 6, 3, 1) and (3, 3, 6, 4), respectively.

Lemma 5.6. We define the matrices N_{1} = A(B + xI)(B + x̄I), N_{2} = yz̄(A + I), N_{3} = z(B + x̄I), N_{4} = z̄A(B + x̄I), N_{5} = ȳ(B + xI), N_{6} = yA(B + xI). For any (i_{1}, …, i_{n}) ∈ {1, …, 6}^{n}, we have

(5.5)  ∑_{T} x^{mi(T)}y^{fd(T)}z^{snd(T)}x̄^{mp(T)}ȳ^{fnd(T)}z̄^{sd(T)} = ⟨W |N_{i_{1}} ⋯ N_{i_{n}}|V ⟩,

where the sum is over T ∈ S_{n} of profile (i_{1}, …, i_{n}).

Proof. We follow the same scheme as in Proposition 4.5, and use Proposition 5.3. Here, the surjective pretableaux of a given profile are in bijection with surjective tableaux of a particular shape. Rather than giving a formal detailed proof, we sketch how to understand the matrices N_{1} through N_{6}, having in mind the proof of Proposition 5.3 and the way surjective tableaux are built recursively.

• The kth co-corner and kth corner correspond to the kth factor BBA in the word (BBA)^{n}. If these are empty (i.e., i_{k} = 1), we can remove the two cells and replace the factor BBA by ABB. With the terms xI and x̄I as seen before, we see that this case correspond to the matrix N_{1} = A(B + xI)(B + x̄I).

• If i_{k} = 2, i.e., the kth co-corner and kth corner both contain a ×, we can remove the two columns containing these ×’s, and remove the factor BB in BBA. But we need to distinguish two cases, depending on whether there is a third × in the same row or not, and if there is not, we also remove the row. This gives a factor A + I, and there is a weight yz̄ because of the doubled × in the corner and co-corner. Hence this case correspond to the matrix N_{2} = yz̄(A+I).

• If i_{k} = 3, i.e., the kth co-corner contains a non-doubled ×, we can remove its row and column, so the kth factor BBA becomes a B + x̄I. There is a weight z for the non-doubled × in the co-corner. Hence this case gives the matrix N_{3} = z(B + x̄I).

• If i_{k} = 4, the difference with the previous case is that the × in the kth co-corner is doubled, so we do not remove its row. So there remains a factor A, and there is a weight z̄ instead of z. Hence this case gives the matrix N_{4} = z̄A(B + x̄I).

• If i_{k} = 5, this is similar to the case when i_{k} = 3. But the weight is ȳ instead of z for the non-doubled × in the corner, and there remains a column of odd index so this gives a factor B + xI instead of B + x̄I. Hence this case gives the matrix N_{5} = ȳ(B + xI).

• If i_{k} = 6, this is similar to the case when i_{k} = 4. But the weight is y instead of z̄ for the doubled × in the corner, and there remains a column of odd index so this gives a factor B + xI instead of B + x̄I. Hence this case gives the matrix N_{6} = yA(B + xI).

When we form the product N_{i_{1}} ⋯ N_{i_{n}}, it is clear that the matrix N_{i_{k}} will impose the conditions on the kth co-corner and corner, and hence ⟨W |N_{i_{1}} ⋯ N_{i_{n}}|V ⟩ is the generating function for elements in S_{n} of profile (i_{1}, …, i_{n}). □

Now we can prove Proposition 5.4.

Proof. We have N = ∑_{i=1}^{6} N_{i}, hence, using Lemma 5.6, we have

⟨W |N^{n}|V ⟩ = ∑_{(i_{1},...,i_{n})∈{1,...,6}^{n}}⟨W |N_{i_{1}} ⋯ N_{i_{n}}|V ⟩

= ∑_{T ∈S_{n}} x^{mi(T)}y^{fd(T)}z^{snd(T)}x̄^{mp(T)}ȳ^{fnd(T)}z̄^{sd(T)} = Γ_{n+1}.

This completes the proof. □

From the definitions of B and A in (5.3), the matrix N defined in (5.4) can be calculated explicitly, and we obtain the following result.

Proposition 5.7. The matrix N = (N_{i,j})_{i,j∈ℕ} is tridiagonal, and for any i ≥ 0 we have N_{i,i} = b_{i} and N_{i,i+1}N_{i+1,i} = λ_{i+1}.

Proof. Straightforward calculations show that N_{i,j} = 0 if |i − j| > 1, N_{i,i} = b_{i}, and

(5.6)  N_{i,i+1} = (i + 1)(z + ȳ + i),  N_{i+1,i} = (x + z̄ + i)(y + x̄ + i).

This gives indeed N_{i,i+1}N_{i+1,i} = λ_{i+1}. □

As in the case of alternative tableaux in the previous section, the previous two propositions mean that the continued fraction expansion given in (1.4) can be derived from the combinatorial interpretation in terms of escaliers and the matrix Ansatz for escaliers given in Proposition 5.3.

Remark 5.8. Observe that N ≠ M since the non-diagonal coefficients are not the same, but the two matrices are equal after a permutation of the variables (x, y, z, x̄, ȳ, z̄). However, there is a priori no simple way to link the matrices M_{i} with the matrices N_{i}, so we tend to think that, despite the similarities in the method, there are two really different ways to obtain the continued fraction from a combinatorial model using the matrix Ansatz approach.

It is natural to ask if there is a bijection between T_{n} and S_{n} preserving the six statistics for Γ_{n}. From the fact that the recurrence relation can be verified on both sets, in theory it might be possible to describe such a bijection recursively. It would be quite interesting to give a better answer to this question by providing a direct bijection between our alternative tableaux and Dumont’s escaliers.

Conclusion

Our main result is the new combinatorial interpretation of Γ_{n} in terms of alternative tableaux. We obtain two new proofs of Dumont’s conjecture, with the same method applied to the two different combinatorial interpretations of Γ_{n}. What is interesting about these proofs is that they fit into the general framework developed in [1], linking J-fractions, operators satisfying certain commutation relations, and combinatorial objects.

Acknowledgement

I thank Dominique Dumont, Dominique Foata, Jiang Zeng, Xavier Viennot and Sylvie Corteel for conversations and encouragements.

References

[1] S. Corteel, M. Josuat-Vergès and L.K. Williams, Matrix Ansatz, orthogonal polynomials and permutations, to appear in Adv. Appl. Math. (2010).

[2] S. Corteel and L.K. Williams, Tableaux combinatorics for the asymmetric exclusion process, Adv. Appl. Math. 39(3) (2007), 293–310.

[3] B. Derrida, M.R. Evans, V. Hakim and V. Pasquier, Exact solution of a 1D asymmetric exclusion model using a matrix formulation, J. Phys. A 26 (1993), 1493–1517.

[4] D. Dumont, Conjectures sur des symétries ternaires liées au nombres de Genocchi, Discrete Math. 139 (1995), 469–472.

[5] D. Dumont and D. Foata, Une propriété de symétrie des nombres de Genocchi, Bull. Soc. Math. France 104 (1976), 433–451.

[6] P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 41 (1982), 145–153.

[7] I. Gessel and J. Zeng, unpublished.

[8] R. Koekoek and R.F. Swarttouw, The Askey-scheme of hypergeometric orthogonal polynomials and its q-analogue, Delft University of Technology, Report no. 98–17 (1998).

[9] P. Nadeau, The structure of alternative tableaux, arχiv:0908.4050v2.

[10] A. Randrianarivony, Polynômes de Dumont–Foata généralisés, Sém. Lothar. Combin. 32 (1994), Article B32d, 12 pp.

[11] A. Randrianarivony and J. Zeng, Sur une extension des nombres d’Euler et les records des permutations alternantes, J. Combin. Theory Ser. A 68 (1994), 86–99.

[12] X.G. Viennot, Interprétations combinatoires des nombres d’Euler et de Genocchi, séminaire de théorie des nombres de l’Université Bordeaux I, 1981.

[13] X.G. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process, talk at the Isaac Newton Institute, April 2008.

http://www.newton.ac.uk/webseminars/pg+ws/2008/csm/csmw04/0423/viennot/

[14] J. Zeng, Sur quelques propriétés de symétrie des nombres de Genocchi, Discrete Math. 153 (1996), 319–333.

LRI, Université Paris-Sud, Bât. 490, 91405 Orsay, FRANCE E-mail address: josuat@lri.fr