Séminaire Lotharingien de Combinatoire 67 (2012), Article B67c

A SYMMETRICAL q-EULERIAN IDENTITY

GUO-NIU HAN, ZHICONG LIN, AND JIANG ZENG

Abstract. We find a q-analog of the following symmetrical identity involving binomial coefficients \binom{n}{m} and Eulerian numbers A_{n,m}, due to Chung, Graham and Knuth [J. Comb., 1 (2010), 29–38]:

∑_{k≥0} \binom{a + b}{k}A_{k,a−1} = ∑_{k≥0} \binom{a + b}{k}A_{k,b−1}.

We give two proofs, using generating function and bijections, respectively.

1. Introduction

The Eulerian polynomials A_{n}(t) are defined by the exponential generating function

∑_{n≥0} A_{n}(t)\frac{z^{n}}{n!} = \frac{(1 − t)e^{z}}{e^{zt} − te^{z}} .  (1.1)

The classical Eulerian numbers A_{n,k} are the coefficients of the polynomial A_{n}(t), i.e., A_{n}(t) = ∑_{k=0}^{n} A_{n,k}t^{k}. Recently, Chung, Graham and Knuth [2] noticed that if we modify the value of A_{0}(t), which is 1 by (1.1), by taking the convention that A_{0}(t) = A_{0,0} = 0, then the following symmetrical identity holds:

∑_{k≥0} \binom{a + b}{k}A_{k,a−1} = ∑_{k≥0} \binom{a + b}{k}A_{k,b−1} (a, b > 0).  (1.2)

Equivalently, instead of (1.1), we define the Eulerian polynomials by the generating function

∑_{n≥0} A_{n}(t)\frac{z^{n}}{n!} = \frac{(1 − t)e^{z}}{e^{zt} − te^{z}} − 1 = \frac{e^{z} − e^{tz}}{e^{zt} − te^{z}} .  (1.3)

At the end of [2], the authors asked for, among other unsolved problems, a q-analog of (1.2). The aim of this paper is to give such an extension and provide two proofs, of which one is analytical and another one is combinatorial.

We first introduce some q-notations. The q-shifted factorial (z; q)_{n} is defined by (z; q)_{n} := ∏_{i=0}^{n−1}(1 − zq^{i}) for any positive integer n and (z; q)_{0} = 1. The q-exponential function e(z; q) is defined by

e(z; q) := ∑_{n≥0} \frac{z^{n}}{(q; q)_{n}} .

Several q-analogs of (1.1) have been proposed in the literature (see [6]). Inspired by the recent work of Shareshian and Wachs [6], we consider the following q-analog of (1.3):

∑_{n≥0} A_{n}(t, q)\frac{z^{n}}{(q; q)_{n}} = \frac{e(z; q) − e(tz; q)}{e(tz; q) − t e(z; q)}.  (1.4)

The q-Eulerian polynomials A_{n}(t, q) have many remarkable properties analogous to Eulerian polynomials, see Shareshian and Wachs [6] and Foata and Han [4]. The q-Eulerian numbers A_{n,k}(q) are then defined by

A_{n}(t, q) = ∑_{k=0}^{n} A_{n,k}(q)t^{k} (n ≥ 0).

The first few terms of A_{n,k}(q) are

A_{0,0}(q) = 0, A_{1,0}(q) = 1, A_{2,0}(q) = 1, A_{2,1}(q) = 1, A_{3,0}(q) = 1, A_{3,1}(q) = 2 + q + q^{2},

and A_{3,2}(q) = 1. Also, replacement of t by t^{−1} and of z by tz in (1.4) yields that t^{n}A_{n}(t^{−1}, q) = tA_{n}(t, q). Thus we have the symmetrical property

A_{n,k}(q) = A_{n,n−k−1}(q).  (1.5)

Recall that the q-binomial coefficients [ \begin{matrix}n \\ k \end{matrix}]_{q} are defined by

[\begin{matrix}n \\ k \end{matrix}]_{q} := \frac{(q; q)_{n}}{(q; q)_{n−k}(q; q)_{k}} for 0 ≤ k ≤ n,

and [ \begin{matrix}n \\ k \end{matrix}]_{q} = 0 if k < 0 or k > n.

The following symmetrical identity involving both the q-binomial coefficients [ \begin{matrix}n \\ k \end{matrix}]_{q} and q-Eulerian numbers A_{n,k}(q) is a true q-analog of (1.2).

Theorem 1. For any positive integers a and b, we have the q-symmetrical identity

∑_{k≥0} [\begin{matrix}a + b \\ k \end{matrix}]_{q}A_{k,a−1}(q) = ∑_{k≥0} [\begin{matrix}a + b \\ k \end{matrix}]_{q}A_{k,b−1}(q).  (1.6)

We shall first give a generating function proof of (1.6) in Section 2 and then a combinatorial proof in Section 3. We conclude the paper with some further extensions and remarks.

2. A generating function proof of (1.6)

It follows from (1.4) that

(e(tz; q) − t e(z; q)) ∑_{n≥0} A_{n}(t, q)\frac{z^{n}}{(q; q)_{n}} = ∑_{k} \frac{(1 − t^{k})z^{k}}{(q; q)_{k}} .  (2.1)

A SYMMETRICAL q-EULERIAN IDENTITY 3

Now,

e(tz; q) ∑_{n≥0} A_{n}(t, q)\frac{z^{n}}{(q; q)_{n}} = ∑_{k} \frac{(tz)^{k}}{(q; q)_{k}} ∑_{n,i} A_{n,i}(q)t^{i} \frac{z^{n}}{(q; q)_{n}}

= ∑_{k,n,i} [\begin{matrix}n + k \\ k \end{matrix}]_{q}A_{n,i}(q)t^{i+k} \frac{z^{n+k}}{(q; q)_{n+k}}

= ∑_{k,n,i} [\begin{matrix}n \\ k \end{matrix}]_{q}A_{n−k,i−k}(q)t^{i} \frac{z^{n}}{(q; q)_{n}} ,

and

t e(z; q) ∑_{n≥0} A_{n}(t, q)\frac{z^{n}}{(q; q)_{n}} = t ∑_{k} \frac{z^{k}}{(q; q)_{k}} ∑_{n,i} A_{n,i}(q)t^{i} \frac{z^{n}}{(q; q)_{n}}

= ∑_{k,n,i} [\begin{matrix}n + k \\ k \end{matrix}]_{q}A_{n,i}(q)t^{i+1} \frac{z^{n+k}}{(q; q)_{n+k}}

= ∑_{k,n,i} [\begin{matrix}n \\ k \end{matrix}]_{q}A_{n−k,i−1}(q)t^{i} \frac{z^{n}}{(q; q)_{n}} .

Substituting the last two expressions in (2.1) and identifying the coefficients of t^{i}z^{n}/(q; q)_{n} on both sides, we obtain

∑_{k} [\begin{matrix}n \\ k \end{matrix}]_{q}A_{n−k,i−k}(q) − ∑_{k} [\begin{matrix}n \\ k \end{matrix}]_{q}A_{n−k,i−1}(q) = \begin{cases}1, & if i = 0 ≠ n, \\ −1, & if i = n ≠ 0, \\ 0, & otherwise. \end{cases}

Setting i = a, n = a + b, and using the symmetrical property (1.5), we obtain (1.6). □

We can also derive q-analogs of other identities in [2]. For example, let H_{n}(t; q) =

∑_{i=0}^{n} [\begin{matrix}n \\ i \end{matrix}]_{q} t^{i} be the Rogers-Szegő polynomials, see [1, p. 49]. Then

e(tz; q)e(z; q) = ∑_{n≥0} \frac{z^{n}}{(q; q)_{n}} H_{n}(t; q).

If we multiply (1.4) by e(tz; q)^{2} − t^{2}e(z; q)^{2} = (e(tz; q) + te(z; q))(e(tz; q) − te(z; q)), then the right-hand side is equal to

(e(tz; q) + te(z; q))(e(z; q) − e(tz; q))

= ∑_{n≥0} \frac{z^{n}}{(q; q)_{n}} ((1 − t)H_{n}(t; q) + (t − t^{n})H_{n}(1; q)) .

On the other hand, we have

(e(tz; q))^{2} ∑_{n≥0} A_{n}(t, q)\frac{z^{n}}{(q; q)_{n}} = ∑_{n,i,k} H_{k}(1; q)[\begin{matrix}n \\ k \end{matrix}]_{q}A_{n−k,i−k}(q)t^{i} \frac{z^{n}}{(q; q)_{n}} ,

and

t^{2}(e(z; q))^{2} ∑_{n≥0} A_{n}(t, q)\frac{z^{n}}{(q; q)_{n}} = ∑_{n,i,k} H_{k}(1; q)[\begin{matrix}n \\ k \end{matrix}]_{q}A_{n−k,i−2}(q)t^{i} \frac{z^{n}}{(q; q)_{n}} .

Hence, identifying the coefficients of t^{i}z^{n}/(q; q)_{n} in these expressions, we arrive at

∑_{k} H_{k}(1; q)[\begin{matrix}n \\ k \end{matrix}]_{q}A_{n−k,i−k}(q) − ∑_{k} H_{k}(1; q)[\begin{matrix}n \\ k \end{matrix}]_{q}A_{n−k,i−2}(q)

= [\begin{matrix}n \\ i \end{matrix}]_{q} − [\begin{matrix}n \\ i − 1 \end{matrix}]_{q} + \begin{cases}H_{n}(1; q), & if i = 1 ≠ n, \\ −H_{n}(1; q), & if i = n ≠ 1, \\ 0, & otherwise. \end{cases}

Of course, we can also multiply (1.4) by e(tz; q)^{r} − t^{r}e(z; q)^{r} for any integer r ≥ 1 and derive a q-analog of the more general (and complicated) identity in [2].

3. A combinatorial proof of (1.6)

For each permutation π = π_{1}π_{2} … π_{n} of [n] := {1, …, n}, define the following four statistics:

exc(π) := |{i : 1 ≤ i ≤ n, π_{i} > i}|;

des(π) := |{i : 1 ≤ i ≤ n − 1, π_{i} > π_{i+1}}|;

maj(π) := ∑_{π_{i}>π_{i+1}} i;

inv(π) := |{(i, j) : i < j, π_{i} > π_{j}}|;

called number of excedances, number of descents, major index and inversion number, respectively. It is well-known that the Eulerian number A_{n,k} counts the number of permutation of [n] with k descents or k excedances.

Let 𝔖_{n} be the set of permutations of [n]. Shareshian and Wachs [6] prove that

A_{n}(t, q) = ∑_{π∈𝔖_{n}} q^{(maj − exc)π}t^{exc π}.

For our purpose we shall use another interpretation of A_{n}(t, q) due to Foata and Han [3,4]. This interpretation is based on Gessel’s hook factorization of permutations [5], which we recall now. A word w = x_{1}x_{2} … x_{m} is called a hook if x_{1} > x_{2} and either m = 2, or m ≥ 3 and x_{2} < x_{3} < … < x_{m}. Clearly, each permutation π = π_{1}π_{2} … π_{n} admits a unique factorization, called its hook factorization, pτ_{1}τ_{2} … τ_{r}, where p is an increasing word and each factor τ_{1}, τ_{2}, …, τ_{k} is a hook. To derive the hook factorization of a permutation, one can start from the right and factor out each hook step by step. For each i let inv τ_{i} denote the number of inversions of τ_{i} and define

lec(π) := ∑_{1≤i≤k} inv(τ_{i}).  (3.1)

For example, the hook factorization of π = 1 3 4 14 12 2 5 11 15 8 6 7 13 9 10 is

1 3 4 14 |12 2 5 11 15 |8 6 7 |13 9 10.

Hence p = 1 3 4 14, τ_{1} = 12 2 5 11 15, τ_{2} = 8 6 7, τ_{3} = 13 9 10 and

lec(π) = inv(12 2 5 11 15) + inv(8 6 7) + inv(13 9 10) = 7.

Let pτ_{1}τ_{2} … τ_{r} be the hook factorization of a permutation π. Let A_{0} (respectively A_{i}, 1 ≤ i ≤ r) denote the set of all letters in the word p (respectively in the hook τ_{i}). We call A_{0} = cont(p) (respectively A_{i} = cont(τ_{i}) (1 ≤ i ≤ r)) the content of p (respectively of the hook τ_{i}) and content of π the sequence Cont(π) = (A_{0}, A_{1}, …, A_{r}). The statistic (inv − lec)π is equal to the number of pairs (k, l) such that k ∈ A_{i}, l ∈ A_{j}, k > l and i < j, a number we shall denote by inv(A_{0}, A_{1}, …, A_{r}).

From Foata and Han [3,4], we derive the following combinatorial interpretation:

A_{n}(t, q) = ∑_{π∈𝔖_{n}} q^{(inv − lec)π}t^{lec π}.

Therefore

A_{n,k}(q) = _{∑_{π∈𝔖_{n}} ; lec π=k}q^{(inv − lec)π}.  (3.2)

Recall [1] that the q-multinomial coefficient

[\begin{matrix}n \\ a_{0}, a_{1}, …, a_{k} \end{matrix}]_{q} = \frac{(q; q)_{n}}{(q; q)_{a_{0}}(q; q)_{a_{1}} ⋯ (q; q)_{a_{k}}}

has the interpretation

[\begin{matrix}n \\ a_{0}, a_{1}, …, a_{k} \end{matrix}]_{q} = ∑_{(A_{0},A_{1},...,A_{k})} q^{inv(A_{0},A_{1},...,A_{k})},  (3.3)

where the sum is over all ordered partitions (A_{0}, A_{1}, …, A_{k}) of [n] such that |A_{i}| = a_{i}, 0 ≤ i ≤ k.

We will give a combinatorial proof of (1.6) using (3.2) and (3.3). As a warm-up, we first prove the symmetry property (1.5) by constructing an explicit involution on permutations.

Lemma 2. There is an involution π ↦ σ on 𝔖_{n} satisfying

lec(π) = n − 1 − lec(σ), and (inv − lec)π = (inv − lec)σ.

Proof. Let τ be a hook with inv(τ) = k and cont(τ) = {x_{1}, …, x_{m}}, where x_{1} < … < x_{m}. Define d(τ) = x_{m−k+1}x_{1} … x_{m−k}x_{m−k+2} … x_{m}. Clearly d(τ) is the unique hook satisfying cont(d(τ)) = cont(τ) and inv(d(τ)) = m − k = | cont(τ)| − inv(τ).

Let τ be a word with inv(τ) = k and cont(τ) = {x_{1}, …, x_{m}}, where x_{1} < … < x_{m}. Define d′(τ) = x_{m−k}x_{1} … x_{m−k−1}x_{m−k+1} … x_{m}. Clearly d′(τ) is the unique word satisfying cont(d′(τ)) = cont(τ) and inv(d′(τ)) = m − k − 1 = | cont(τ)| − inv(τ) − 1.

Let π = pτ_{1}τ_{2} … τ_{r} be the hook factorization of π ∈ 𝔖_{n}.

• If p ≠ ∅, let σ = d′(p)d(τ_{1})d(τ_{2}), …, d(τ_{r}).

• If p = ∅, let σ = d′(τ_{1})d(τ_{2})d(τ_{3}) … d(τ_{r}). Since d and d′ are two involutions, it is routine to check that such a mapping is an involution with the required properties. □

For each fixed positive integer n, a two-pix-permutation of [n] is a sequence of words

v = (p_{1}, τ_{1}, τ_{2}, …, τ_{r−1}, τ_{r}, p_{2})  (3.4)

satisfying the following conditions: (C1) p_{1} and p_{2} are two increasing words, possibly empty; (C2) τ_{1}, …, τ_{r} are hooks for some positive integer r; (C3) The concatenation p_{1}τ_{1}τ_{2} … τ_{r−1}τ_{r}p_{2} of all components of v is a permutation of

[n]. We also extend the two statistics to the two-pix-permutations by

lec(v) = inv(τ_{1}) + inv(τ_{2}) + ⋯ + inv(τ_{r}),
inv(v) = inv(p_{1}τ_{1}τ_{2} … τ_{r−1}τ_{r}p_{2}).

It follows that

(inv − lec)v = inv(cont(p_{1}), cont(τ_{1}), cont(τ_{2}), …, cont(τ_{r}), cont(p_{2})).  (3.5)

Lemma 3. The generating function of all two-pix-permutations v of n such that lec(v) = s by the statistic inv − lec is

∑_{k≥0} [\begin{matrix}n \\ k \end{matrix}]_{q}A_{k,s}(q).  (3.6)

Proof. By the hook factorization, the two-pix-permutation v in (3.4) is in bijection with the pair (σ, p_{2}), where σ = p_{1}τ_{1}τ_{2} … τ_{r−1}τ_{r} is a permutation on [n] \ cont(p_{2}) and p_{2} is an increasing word. Thus, by (3.2), (3.3), and (3.5), the generating function of all two-pix-permutations v of [n] such that lec(v) = s and |p_{2}| = n − k with respect to the weight

q^{(inv − lec)(v)} is [ \begin{matrix}n \\ k \end{matrix}]_{q} A_{k,s}(q). □

Lemma 4. There is a bijection v ↦ u on the set of all two-pix-permutations of [n] satisfying

lec(v) = n − 2 − lec(u), and (inv − lec)v = (inv − lec)u.

Proof. We give an explicit construction of the bijection. Let v be a two-pix-permutation and write

v = (τ_{0}, τ_{1}, τ_{2}, …, τ_{r−1}, τ_{r}, τ_{r+1}),

where τ_{0} = p_{1} and τ_{r+1} = p_{2}. If τ_{i} (respectively τ_{j}) is the leftmost (respectively rightmost) non-empty word (clearly i = 0, 1 and j = r, r+1), we can write v in the following compact way by removing the empty words at the beginning or at the end:

v = (τ_{i}, τ_{i+1}, …, τ_{j−1}, τ_{j}).  (3.7)

It is easy to see that the above procedure is reversible by adding some necessary empty words at the two ends of the compact form (3.7). Now we work with the compact form. Recall that

(inv − lec)v = inv(cont(τ_{i}), cont(τ_{i+1}), …, cont(τ_{j−1}), cont(τ_{j}))  (3.8)

and lec(v) = ∑_{k=i}^{j} lec(τ_{k}).

If i = j, then only one word τ_{i} is in the sequence v. We define u = (∅, σ_{i}, ∅), where σ_{i} is the unique word (hook) with content [n] such that lec(σ_{i}) = n − 2 − lec(τ_{i}).

If j > i, we define the two-pix-permutation u by

u = (d′(τ_{i}), d(τ_{i+1}), d(τ_{i+2}), …, d(τ_{j−1}), d′(τ_{j})),

where d and d′ are two involutions defined in the proof of Lemma 2.

Since lec(d′(τ_{i})) = | cont(τ_{i})| − 1 − lec(τ_{i}), lec(d′(τ_{j})) = | cont(τ_{j})| − 1 − lec(τ_{j}) and lec(d′(τ_{k})) = | cont(τ_{k})| − lec(τ_{k}) for k ≠ i, j, we have

lec(u) = ∑ | cont(τ_{k})| − 2 − lec(v) = n − 2 − lec(v).

Finally it follows from (3.8) that (inv − lec)u = (inv − lec)v.

We give an example to illustrate the bijection. Let v = (27, 6389, 514, ∅). Then v is a two-pix-permutation of [9] and inv(v) = 19, lec(v) = 3, (inv − lec)v = 16. The compact form is (27, 6389, 514), so that

u = (d′(27), d(6389), d′(514) = (72, 9368, 145).

Since the first word 72 is not increasing, we obtain the standard form by adding the empty word at the beginning, so that u = (∅, 72, 9368, 145). Hence inv(u) = 20, lec(u) = 4, and (inv − lec)u = 16. □

Combining Lemmas 2, 3 and 4, we obtain a combinatorial proof of (1.6).

4. Further extensions and remarks

The classical Eulerian polynomials correspond to the generating function of descent numbers of symmetric groups. Let r ≥ 1 be an integer. As a natural extension of (1.4), we consider the polynomial A_{n}^{(r)}(t, q) defined by the generating function

\frac{e(z; q^{r}) − e(t^{r}z; q^{r})}{e(t^{r}z; q^{r}) − te(z; q^{r})} = ∑_{n≥1} A_{n}^{(r)}(t, q)\frac{z^{n}}{(q^{r}; q^{r})_{n}} .  (4.1)

It is easy to see that A_{n}^{(r)}(1, 1) = r^{n}n!, which is the cardinality of C_{r} ≀ 𝔖_{n}, that is, the wreath product of a cyclic group C_{r} of order r with the symmetric group 𝔖_{n}. Introduce the coefficients A_{n,i}^{(r)} by

A_{n}^{(r)}(t, q) = ∑_{i} A_{n,i}^{(r)}(q)t^{i}.  (4.2)

The generating function proof of (1.6) can be applied to derive immediately the identity

∑_{k} [\begin{matrix}n \\ k \end{matrix}]_{q^{r}}A_{k,rn−i−1}^{(r)}(q) = ∑_{k} [\begin{matrix}n \\ k \end{matrix}]_{q^{r}}A_{k,i−1}^{(r)}(q)  (4.3)

for positive integers i and n such that i ≠ rn.

Let r and n be two positive integers. Let A = {a, b, …} be any subset of [n]. We define the r-colored version of A by

A^{r} := {a^{1}, b^{1}, …, a^{2}, b^{2}, …, …, a^{r}, b^{r}, …}.

Order the elements of [n]^{r} by

1^{1} < 1^{2} … < 1^{r} < 2^{1} < 2^{2} … < 2^{r} < … < n^{1} < n^{2} < … < n^{r}.

A pix-r-colored-word is a sequence of colored words

w = (p, τ_{1}, τ_{2}, …, τ_{k})

satisfying the following conditions: (C1) p is an increasing word, with content A_{0}^{r}, the r-colored version of A_{0}, possibly

empty; (C2) τ_{i} (1 ≤ i ≤ k) are hooks, with content A_{i}^{r}, the r-colored version of A_{i}, and the

positive integer k is not fixed; (C3) (A_{0}, A_{1}, …, A_{k}) is an ordered partition of [n]. Let 𝒲_{n,r} be the set of all pix-r-colored-words of [n]. For each w ∈ 𝒲_{n,r} we define two statistics by

inv_{r}(w) = inv(pτ_{1}τ_{2} … τ_{r−1}τ_{r}),
lec_{r}(w) = inv(τ_{1}) + ⋯ + inv(τ_{k}).

Proposition 5. Let A_{n}^{(r)}(t, q) be defined by (4.1). Then

∑_{σ∈𝒲_{n,r}} q^{(inv_{r} − lec_{r})(σ)}t^{lec_{r}(σ)} = A_{n}^{(r)}(t, q).

Proof. By definition and (3.3), we have

∑_{σ∈𝒲_{n,r}} q^{(inv_{r} − lec_{r})(σ)}t^{lec_{r}(σ)} = _{∑_{a_{0}+a_{1}+...+a_{k}=n} ; a_{i}≥1} ∏_{1≤i≤k} P_{ra_{i}}(t)_{∑_{(A_{0},A_{1},...,A_{k})} ; #A_{i}=a_{i}}q^{inv_{r}(A_{0},A_{1},...,A_{k})}

= _{∑_{a_{0}+a_{1}+...+a_{k}=n} ; a_{i}≥1} [\begin{matrix}n \\ a_{0}, a_{1}, …, a_{k} \end{matrix}]_{q^{r}} ∏_{1≤i≤k} P_{ra_{i}}(t),

where P_{m}(t) := t + t^{2} + … + t^{m−1}. So the generating function is

∑_{n,i} ∑_{σ∈𝒲_{n,r}} q^{(inv_{r} − lec_{r})(σ)}t^{lec_{r}(σ)} \frac{z^{n}}{(q^{r}; q^{r})_{n}}

= ∑_{n≥0}_{∑_{a_{0}+a_{1}+...+a_{k}=n} ; a_{i}≥1} [\begin{matrix}n \\ a_{0}, a_{1}, …, a_{k} \end{matrix}]_{q^{r}} ∏_{1≤i≤k} P_{ra_{i}}(t)\frac{z^{n}}{(q^{r}; q^{r})_{n}}

= (∑_{a≥0} \frac{z^{a}}{(q^{r}; q^{r})_{a}} ) (1 − ∑_{b≥1} P_{rb}(t)\frac{z^{b}}{(q^{r}; q^{r})_{b}} )^{−1}

= e(z; q^{r}) (1 − ∑_{b≥1} \frac{t − t^{rb}}{1 − s} \frac{z^{b}}{(q^{r}; q^{r})_{b}} )^{−1}

= \frac{(1 − t)e(z; q^{r})}{e(t^{r}z; q^{r}) − t e(z; q^{r})}.

This completes the proof in view of (4.1). □

Similarly, we can define two-pix-r-colored-words to be sequences of colored words

w = (p_{1}, τ_{1}, τ_{2}, …, τ_{k}, p_{2})

with the following conditions: (C1) p_{1} and p_{2} are increasing words, with content A_{0}^{r} and B_{0}^{r}, possibly empty; (C2) τ_{i} (1 ≤ i ≤ k) are hooks, with content A_{i}^{r}, the r-colored version of A_{i}, and the

positive integer k is not fixed; (C3) (A_{0}, A_{1}, …, A_{k}, B_{0}) is an ordered partition of [n]. Clearly we can give a combinatorial proof of (4.3) by applying the following generalization of Lemma 4.

Proposition 6. There is a bijection v ↦ u on the set of all two-pix-r-colored-words such that

lec_{r} v = rn − 2 − lec_{r} u, and (inv_{r} − lec_{r})v = (inv_{r} − lec_{r})u.

When r = 1, through Gessel’s hook factorization, we can translate the statistic (inv_{r}, lec_{r}) to 𝔖_{n}. It would be interesting to see whether there is an analogous hook factorization for general r ≥ 1 so that we can translate our (inv_{r}, lec_{r}) defined on 𝒲_{n,r} to C_{r} ≀ 𝔖_{n}.

We conclude this paper with another symmetric identity for the Eulerian numbers. Notice that for any positive integers n and k we have

[\begin{matrix}2n \\ 2k + 1 \end{matrix}]_{−1} = 0 and [\begin{matrix}2n \\ 2k \end{matrix}]_{−1} = \binom{n}{k}.

It is known [8, Cor. 6.2] that if dk = n and ω_{d} is a primitive d^{th} root of unity, then

A_{n}(t, ω_{d}) = A_{k}(t) (\frac{1 − t^{d}}{1 − t} )^{k} .

In particular, if d = 2, then ω_{d} = −1. Hence, assuming that a+b is even, the substitution q = −1 in (1.6) yields

∑_{k≥0} \binom{\frac{a+b}{2}}{k} ∑_{i+j=a−1} \binom{k}{i}A_{k,j} = ∑_{k≥0} \binom{\frac{a+b}{2}}{k} ∑_{i+j=b−1} \binom{k}{i}A_{k,j}.  (4.4)

This identity can be rephrased in the form

∑_{k≥0} \binom{c + d}{k} ∑_{i+j=2c−1} \binom{k}{i}A_{k,j} = ∑_{k≥0} \binom{c + d}{k} ∑_{i+j=2d−1} \binom{k}{i}A_{k,j}

and

∑_{k≥0} \binom{c + d − 1}{k} ∑_{i+j=2(c−1)} \binom{k}{i}A_{k,j} = ∑_{k≥0} \binom{c + d − 1}{k} ∑_{i+j=2(d−1)} \binom{k}{i}A_{k,j}

for any positive integers c and d.

The last two symmetrical identities involving binomial coefficients and Eulerian numbers cry out for a combinatorial interpretation.

Acknowledgement. This work was partially supported by the grant ANR-08-BLAN-0243-03.

References

[1] George E. Andrews, The Theory of Partitions, Reading MA: Addison-Wesley, 1976.

[2] Fan Chung, Ron Graham, Don Knuth, A symmetrical Eulerian identity, J. Comb., 1 (2010), 29–38.

[3] Dominique Foata and Guo-Niu Han, The q-tangent and q-secant numbers via basic Eulerian polynomials, Proc. Amer. Math. Soc., 138 (2009), 385–393.

[4] Dominique Foata and Guo-Niu Han, Fix-mahonian calculus III; a quadruple distribution, Monatsh. Math., 154 (2008), 177–197.

[5] Ira Gessel, A coloring problem, Amer. Math. Monthly, 98 (1991), 530–533.

[6] John Shareshian and Michelle L. Wachs, Eulerian quasisymmetric function, Adv. in Math., 46 (2011), 536–562.

[7] John Shareshian and Michelle L. Wachs, q-Eulerian polynomials: excedance number and major index, Electron. Res. Announc. Amer. Math. Soc., 13 (2007), 33–45.

[8] Bruce Sagan, John Shareshian and Michelle L. Wachs, Eulerian quasisymmetric functions and cyclic sieving, Adv. in Appl. Math., 46 (2011), 536–562.

(Guo-Niu Han) I.R.M.A. UMR 7501, Université de Strasbourg et CNRS, France

E-mail address: guoniu.han@unistra.fr

(Zhicong Lin) Department of Mathematics and Statistics, Lanzhou University, China, and Institut Camille Jordan, UMR 5208 du CNRS, Université de Lyon, Université Lyon 1, France

E-mail address: lin@math.univ-lyon1.fr

(Jiang Zeng) Institut Camille Jordan, UMR 5208 du CNRS, Université de Lyon, Université Lyon 1, France

E-mail address: zeng@math.univ-lyon1.fr