# On some generalized q-Eulerian polynomials

Zhicong Lin

Department of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, P.R. China
Institut Camille Jordan, Université Lyon 1, 43 boulevard du 11 novembre 1918, 69622 Villeurbanne cedex, France

**Abstract.** The $(q, r)$-Eulerian polynomials are the $(\text{maj}-\text{exc}, \text{fix}, \text{exc})$ enumerative polynomials of permutations. Using Shareshian and Wachs' exponential generating function of these Eulerian polynomials, Chung and Graham proved two symmetrical $q$-Eulerian identities and asked for bijective proofs. We provide such proofs using Foata and Han's three-variable statistic $(\text{inv}-\text{lec}, \text{pix}, \text{lec})$. We also prove a new recurrence formula for the $(q, r)$-Eulerian polynomials and study a $q$-analogue of Chung and Graham's restricted Eulerian polynomials. In particular, we obtain a symmetrical identity for these restricted $q$-Eulerian polynomials with a combinatorial proof.

**Résumé.** Les $(q, r)$-polynômes Eulériens sont les polynomômes énumératives des permutations par rapport au poids $(\text{maj}-\text{exc}, \text{fix}, \text{exc})$. En utilisant la fonction génératrice de ces polynômes Eulériens due à Shareshian et Wachs, Chung et Graham ont démontré deux identités symétriques $q$-Eulériennes et demandé des preuves bijectives. Nous donnons de telles preuves en utilisant les statistiques trivariées $(\text{inv}-\text{lec}, \text{pix}, \text{lec})$ de Foata et Han. Nous démontrons aussi une nouvelle récurrence pour ces $(q, r)$-polynômes Eulériens et étudions un $q$-analogue des polynômes Eulériens restreints de Chung et Graham. En particulier, nous obtenons une identité symétrique pour ces $q$-polynômes Eulériens restreints avec une preuve combinatoire.

**Keywords:** Eulerian numbers; symmetrical Eulerian identities; hook factorization; descents; admissible inversions

## 1 Introduction

The Eulerian polynomials $A_n(t) := \sum_{k=0}^{n} A_{n,k} t^k$ are defined by the exponential generating function

$$ \sum_{n \ge 0} A_n(t) \frac{z^n}{n!} = \frac{(1-t)e^z}{e^{zt} - t e^z}. \qquad (1) $$

The coefficients $A_{n,k}$ are called *Eulerian numbers*. The Eulerian numbers arise in a variety of contexts in mathematics. Let $\mathfrak{S}_n$ denote the set of permutations of $[n] := \{1, 2, \dots, n\}$. For each $\pi \in \mathfrak{S}_n$, a value $i$, $1 \le i \le n-1$, is an *excedance* (resp. *descent*) of $\pi$ if $\pi(i) > i$ (resp. $\pi(i) > \pi(i+1)$). Denote by $\text{exc}(\pi)$ and $\text{des}(\pi)$ the number of excedances and descents of $\pi$, respectively. It is well-known that the Eulerian number $A_{n,k}$ counts permutations in $\mathfrak{S}_n$ with $k$ descents (or $k$ excedances), that is $A_n(t) = \sum_{\pi \in \mathfrak{S}_n} t^{\text{des} \pi} = \sum_{\pi \in \mathfrak{S}_n} t^{\text{exc} \pi}$. The reader is referred to [7] for some leisurely historical introductions of Eulerian polynomials and Eulerian numbers.

Several $q$-analogs of Eulerian polynomials with combinatorial meanings have been studied in the literature (see [2, 6, 15, 20]). Recall that the major index, $\text{maj}(\pi)$, of a permutation $\pi \in \mathfrak{S}_n$ is the sum of
all the descents of $\pi$, i.e., $\mathrm{maj}(\pi) := \sum_{\pi(i)>\pi(i+1)} i$. An element $i \in [n]$ is a fixed point of $\pi \in \mathfrak{S}_n$ if $\pi(i) = i$ and we denote by $\mathrm{fix}(\pi)$ the number of fixed points of $\pi$. Define the $(q, r)$-Eulerian polynomials $A_n(t, r, q)$ by the following extension of (1):

$$ \sum_{n \ge 0} A_n(t, r, q) \frac{z^n}{(q; q)_n} = \frac{(1-t)e(rz; q)}{e(tz; q) - te(z; q)}, \qquad (2) $$

where $(q; q)_n := \prod_{i=1}^n (1-q^i)$ and $e(z; q)$ is the $q$-exponential function defined by $e(z; q) := \sum_{n \ge 0} \frac{z^n}{(q; q)_n}$. The following interpretation for $A_n(t, r, q)$ was given by Shareshian and Wachs [16, 18]:

$$ A_n(t, r, q) := \sum_{\pi \in \mathfrak{S}_n} t^{\mathrm{exc} \, \pi} r^{\mathrm{fix} \, \pi} q^{(\mathrm{maj}-\mathrm{exc}) \, \pi}. \qquad (3) $$

These polynomials have attracted the attention of several authors (cf. [8, 9, 10, 11, 13, 14, 17]).

Let $A_n(t, q) = A_n(t, 1, q)$. Define the $q$-Eulerian numbers $A_{n,k}(q)$ and the fixed point $q$-Eulerian numbers $A_{n,k}^{(j)}(q)$:

$$ A_n(t, q) = \sum_k A_{n,k}(q) t^k \quad \text{and} \quad A_n(t, r, q) = \sum_{j,k} A_{n,k}^{(j)}(q) r^j t^k. $$

By (3), we have the following interpretations

$$ A_{n,k}(q) = \sum_{\substack{\pi \in \mathfrak{S}_n \\ \mathrm{exc}\pi = k}} q^{(\mathrm{maj}-\mathrm{exc})\pi} \quad \text{and} \quad A_{n,k}^{(j)}(q) = \sum_{\substack{\pi \in \mathfrak{S}_n \\ \mathrm{exc}\pi = k \\ \mathrm{fix}\pi = j}} q^{(\mathrm{maj}-\mathrm{exc})\pi}. \qquad (4) $$

Recall that the $q$-binomial coefficients $\begin{bmatrix} n \\ k \end{bmatrix}_q$ are defined by $\begin{bmatrix} n \\ k \end{bmatrix}_q := \frac{(q;q)_n}{(q;q)_{n-k}(q;q)_k}$ for $0 \le k \le n$, and $\begin{bmatrix} n \\ k \end{bmatrix}_q = 0$ if $k < 0$ or $k > n$.

Answering a question of Chung et al. [5], Han et al. [13] found and proved the following symmetrical $q$-Eulerian identity:

$$ \sum_{k \ge 1} \begin{bmatrix} a+b \\ k \end{bmatrix}_q A_{k,a-1}(q) = \sum_{k \ge 1} \begin{bmatrix} a+b \\ k \end{bmatrix}_q A_{k,b-1}(q), \qquad (5) $$

where $a, b$ are integers with $a, b \ge 1$. Besides a generating function proof using (2), a bijective proof of (5) was also given in [13]. Recently, through analytical arguments, Chung and Graham [4] derived from (2) the following two further symmetrical $q$-Eulerian identities:

$$ \sum_{k \ge 1} (-1)^k \begin{bmatrix} a+b \\ k \end{bmatrix}_q q^{\binom{a+b-k}{2}} A_{k,a}(q) = \sum_{k \ge 1} (-1)^k \begin{bmatrix} a+b \\ k \end{bmatrix}_q q^{\binom{a+b-k}{2}} A_{k,b}(q), \qquad (6) $$

$$ \sum_{k \ge 1} \begin{bmatrix} a+b+j+1 \\ k \end{bmatrix}_q A_{k,a}^{(j)}(q) = \sum_{k \ge 1} \begin{bmatrix} a+b+j+1 \\ k \end{bmatrix}_q A_{k,b}^{(j)}(q), \qquad (7) $$

where $a, b, j$ are integers with $a, b \ge 1$ and $j \ge 0$, and asked for bijective proofs. Our first aim is to provide such proofs using another interpretation of $A_n(t, r, q)$ introduced by Foata and Han [9], which was already shown to be successful in the bijective proof of (5) in [13].
Next, for $1 \le j \le n$, we shall define the restricted q-Eulerian polynomial $B_n^{(j)}(t, q)$ by the exponential generating function:

$$ \sum_{n \ge j} B_n^{(j)}(t, q) \frac{z^{n-1}}{(q; q)_{n-1}} = \left( \frac{A_{j-1}(t, q)(qz)^{j-1}}{(q; q)_{j-1}} \right) \frac{e(tz; q) - te(tz; q)}{e(tz; q) - te(z; q)}. \quad (8) $$

and the restricted q-Eulerian number $B_{n,k}^{(j)}(q)$ by $B_n^{(j)}(t, q) = \sum_k B_{n,k}^{(j)}(q)t^k$. We find the following generalized symmetrical identity for the restricted q-Eulerian polynomials.

**Theorem 1** Let $a, b, j$ be integers with $a, b \ge 1$ and $j \ge 2$. Then

$$ \sum_{k \ge 1} \left[ \binom{a+b+1}{k-1} \right]_q B_{k,a}^{(j)}(q) = \sum_{k \ge 1} \left[ \binom{a+b+1}{k-1} \right]_q B_{k,b}^{(j)}(q). \quad (9) $$

When $q = 1$, the above identity was proved by Chung and Graham [4], who also asked for a bijective proof. We shall give a bijective proof and an analytical proof of (9), the latter leads to a new recurrence formula for $A_n(t, r, q)$.

**Theorem 2** The $(q, r)$-Eulerian polynomials satisfy the following recurrence formula:

$$ A_{n+1}(t, r, q) = rA_n(t, r, q) + tA_n(t, q) + t \sum_{j=1}^{n-1} \left[ \binom{n}{j} \right]_q q^j A_j(t, r, q) A_{n-j}(t, q) \quad (10) $$

for $n \ge 1$ and $A_1(t, r, q) = r$.

This paper is organized as follows. In section 2, we review some preliminaries about the three-variable statistic (inv, pix, lec) and give the bijective proofs of (6) and (7). In section 3, we first prove Theorem 2 and then define a new statistic called “rix”, which together with descents and *admissible inversions* (a statistic on permutations which appears in the context of poset topology [16]) gives another interpretation of $A_n(t, r, q)$. In section 4, we give two combinatorial interpretations of $B_{n,k}^{(j)}(q)$ and two proofs of Theorem 1.

# 2 Bijective proofs of (6) and (7)

## 2.1 Preliminaries

A word $w = w_1w_2...w_m$ on $\mathbb{N}$ is called a *hook* if $w_1 > w_2$ and either $m = 2$, or $m \ge 3$ and $w_2 < w_3 < ... < w_m$. As shown in [12], each permutation $\pi = \pi_1\pi_2...\pi_n$ admits a unique factorization, called its *hook factorization*, $p\tau_1\tau_2...\tau_r$, where $p$ is an increasing word and each factor $\tau_1, \tau_2, ..., \tau_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. Denote by $\text{inv}(w)$ the numbers of *inversions* of a word $w = w_1w_2...w_m$, i.e., the number of pairs $(w_i, w_j)$ such that $i < j$ and $w_i > w_j$. Then we define

$$ \text{lec}(\pi) := \sum_{1 \le i \le k} \text{inv}(\tau_i) \quad \text{and} \quad \text{pix}(\pi) := \text{length of the factor } p. $$
For example, the hook factorization of $\pi = 134141225111586713910$ is
$$13414|12251115|867|13910.$$

Hence $p = 13414$, $\tau_1 = 12251115$, $\tau_2 = 867$, $\tau_3 = 13910$, $\mathrm{pix}(\pi) = 4$ and
$$\mathrm{lec}(\pi) = \mathrm{inv}(12251115) + \mathrm{inv}(867) + \mathrm{inv}(13910) = 7.$$

Let $\mathcal{A}_0, \mathcal{A}_1, \dots, \mathcal{A}_r$ be a series of sets on $\mathbb{N}$. Denote by $\mathrm{inv}(\mathcal{A}_0, \mathcal{A}_1, \dots, \mathcal{A}_r)$ the number of pairs $(k, l)$ such that $k \in \mathcal{A}_i, l \in \mathcal{A}_j, k > l$ and $i < j$. We usually write $\mathrm{cont}(\mathcal{A})$ to denote the set of all letters in a word $\mathcal{A}$. So we have $(\mathrm{inv} - \mathrm{lec})\pi = \mathrm{inv}(\mathrm{cont}(p), \mathrm{cont}(\tau_1), \dots, \mathrm{cont}(\tau_r))$ if $p\tau_1\tau_2\dots\tau_r$ is the hook factorization of $\pi$.

From Foata and Han [9, Theorem 1.4], we derive the following combinatorial interpretations of the $(q, r)$-Eulerian polynomials

$$A_n(t, r, q) = \sum_{\pi \in \mathfrak{S}_n} t^{\mathrm{lec}\pi} r^{\mathrm{pix}\pi} q^{(\mathrm{inv}-\mathrm{lec})\pi}. \qquad (11)$$

Therefore

$$A_{n,k}(q) = \sum_{\substack{\pi \in \mathfrak{S}_n \\ \mathrm{lec}\pi = k}} q^{(\mathrm{inv}-\mathrm{lec})\pi} \quad \text{and} \quad A_{n,k}^{(j)}(q) = \sum_{\substack{\pi \in \mathfrak{S}_n \\ \mathrm{lec}\pi = k \\ \mathrm{pix}\pi = j}} q^{(\mathrm{inv}-\mathrm{lec})\pi}. \qquad (12)$$

It is known [19, Proposition 1.3.17] that the $q$-binomial coefficient has the interpretation

$$\begin{bmatrix} n \\ k \end{bmatrix}_q = \sum_{(A,B)} q^{\mathrm{inv}(A,B)}, \qquad (13)$$

where the sum is over all ordered partitions $(A, B)$ of $[n]$ such that $|A| = k$.

We will give bijective proofs of (6) and (7) using the interpretations in (12) and (13).

**Remark 1** In [9], a bijection on $\mathfrak{S}_n$ that carries the triplet (fix, exc, maj) to (pix, lec, inv) was constructed without being specified. This bijection consists of two steps. The first step (see [9, section 6]) uses the word analogue of Kim-Zeng's decomposition and an updated version of Gessel-Reutenauer standardization to construct a bijection on $\mathfrak{S}_n$ that transforms the triplet (fix, exc, maj) to (pix, lec, imaj), where $\mathrm{imaj}(\pi) := \mathrm{maj}(\pi^{-1})$ for each permutation $\pi$. The second step (see [9, section 7]) uses Foata's second fundamental transformation to carry the triplet (pix, lec, imaj) to (pix, lec, inv). In view of this bijection, one can construct bijective proofs of (5), (6) and (7) using the original interpretations in (4), through the bijective proof of (5) in [13] and our bijective proofs.

To construct our bijective proofs, we need two elementary transformations from [13] that we recall now. Let $\tau$ be a hook with $\mathrm{inv}(\tau) = k$ and $\mathrm{cont}(\tau) = \{x_1, \dots, x_m\}$, where $x_1 < \dots < x_m$. Define

$$d(\tau) = x_{m-k+1}x_1 \dots x_{m-k}x_{m-k+2} \dots x_m. \qquad (14)$$

Clearly, $d(\tau)$ is the unique hook with $\mathrm{cont}(d(\tau)) = \mathrm{cont}(\tau)$ and satisfying $\mathrm{inv}(d(\tau)) = m - k = |\mathrm{cont}(\tau)| - \mathrm{inv}(\tau)$. Let $\tau$ be a hook or an increasing word with $\mathrm{inv}(\tau) = k$ and $\mathrm{cont}(\tau) = \{x_1, \dots, x_m\}$, where $x_1 < \dots < x_m$. Define

$$d'(\tau) = x_{m-k}x_1 \dots x_{m-k-1}x_{m-k+1} \dots x_m. \qquad (15)$$

It is not difficult to see that, $d'(\tau)$ is the unique hook (when $k < m - 1$) or increasing word (when $k = m - 1$) with $\mathrm{cont}(d(\tau)) = \mathrm{cont}(\tau)$ and satisfying $\mathrm{inv}(d(\tau)) = m - k - 1 = |\mathrm{cont}(\tau)| - 1 - \mathrm{inv}(\tau)$.
## 2.2 Bijective proof of (6)

Let $\mathfrak{S}_n(k) = \{\pi \in \mathfrak{S}_n : \text{pix}(\pi) = k\}$ and $\mathcal{D}_n = \mathfrak{S}_n(0)$. We first notice that the left-hand side of (6) has the following interpretation:

$$ \sum_{\substack{\pi \in \mathcal{D}_n \\ \text{lec}\pi = a}} q^{(\text{inv-lec})\pi} = \sum_{k \ge 1} (-1)^{n-k} \begin{bmatrix} n \\ k \end{bmatrix}_q q^{\binom{n-k}{2}} A_{k,a}(q). \quad (16) $$

This interpretation follows immediately from [18, Corollary 4.4] and (11). Note that one can also give a direct combinatorial proof similarly as in [21].

Now, by (16), the symmetrical identity (6) is equivalent to the $j = 0$ case of the following Lemma.

**Lemma 1** For $0 \le j \le n$, there is an involution $\mathbf{v} \mapsto \mathbf{u}$ on $\mathfrak{S}_n(j)$ satisfying

$$ \text{lec}(\mathbf{u}) = n - j - \text{lec}(\mathbf{v}) \quad \text{and} \quad (\text{inv} - \text{lec})\mathbf{u} = (\text{inv} - \text{lec})\mathbf{v}. $$

**Proof:** Let $\mathbf{v} = p\tau_1\tau_2\dots\tau_r$ be the hook factorization of $\mathbf{v} \in \mathfrak{S}_n(j)$, where $p$ is an increasing word and each factor $\tau_1, \tau_2, \dots, \tau_r$ is a hook. We define $\mathbf{u} = pd(\tau_1)\dots d(\tau_r)$, where $d$ is defined in (14). It is easy to check that this mapping is an involution on $\mathfrak{S}_n(j)$ with the desired properties. $\square$

By (12), Lemma 1 gives a simple bijective proof of the following known [4, 18] symmetric property of the fixed point q-Eulerian numbers.

**Corollary 1** For $n, k, j \ge 0$,

$$ A_{n,k}^{(j)}(q) = A_{n,n-j-k}^{(j)}(q). \quad (17) $$

## 2.3 Bijective proof of (7)

Recall [13] that, for a fixed positive integer $n$, a two-pix-permutation of $[n]$ is a sequence of words

$$ \mathbf{v} = (p_1, \tau_1, \tau_2, \dots, \tau_{r-1}, \tau_r, p_2) \quad (18) $$

satisfying the following conditions:

(C1) $p_1$ and $p_2$ are two increasing words, possibly empty;

(C2) $\tau_1, \dots, \tau_r$ are hooks for some positive integer $r$;

(C3) The concatenation $p_1\tau_1\tau_2\dots\tau_{r-1}\tau_r p_2$ of all components of $\mathbf{v}$ is a permutation of $[n]$.

We also extend the two statistics to the two-pix-permutations by

$$ \text{lec}(\mathbf{v}) = \sum_{1 \le i \le r} \text{inv}(\tau_i) \quad \text{and} \quad \text{inv}(\mathbf{v}) = \text{inv}(p_1\tau_1\tau_2\dots\tau_{r-1}\tau_r p_2). $$

It follows that

$$ (\text{inv} - \text{lec})\mathbf{v} = \text{inv}(\text{cont}(p_1), \text{cont}(\tau_1), \text{cont}(\tau_2), \dots, \text{cont}(\tau_r), \text{cont}(p_2)). \quad (19) $$

Let $W_n(j)$ denote the set of all two-pix-permutations with $|p_1| = j$.
**Lemma 2** Let $a, j$ be fixed nonnegative integers. Then

$$ \sum_{\mathbf{v} \in W_n(j)_{\text{lec}\mathbf{v}=a}} q^{(\text{inv-lec})\mathbf{v}} = \sum_{k \ge 1} \begin{bmatrix} n \\ k \end{bmatrix}_q A_{k,a}^{(j)}(q). \qquad (20) $$

**Proof:** By the hook factorization, the two-pix-permutation in (18) is in bijection with the pair $(\sigma, p_2)$, where $\sigma = p_1\tau_1\tau_2\dots\tau_{r-1}\tau_r$ is a permutation on $[n] \setminus \text{cont}(p_2)$ and $p_2$ is an increasing word. Thus, by (12), (13) and (19), the generating function of all two-pix-permutations $\mathbf{v}$ of $[n]$ with $|p_1| = j$ such that $\text{lec}(\mathbf{v}) = a$ and $|p_2| = n-k$ with respect to the weight $q^{(\text{inv-lec})\mathbf{v}}$ is $\begin{bmatrix} n \\ n-k \end{bmatrix}_q A_{k,a}^{(j)}(q)$. $\square$

**Lemma 3** Let $j$ be a fixed nonnegative integer. Then there is an involution $\mathbf{v} \mapsto \mathbf{u}$ on $W_n(j)$ satisfying

$$ \text{lec}(\mathbf{v}) = n - j - 1 - \text{lec}(\mathbf{u}), \quad \text{and} \quad (\text{inv} - \text{lec})\mathbf{v} = (\text{inv} - \text{lec})\mathbf{u}. $$

**Proof:** We give an explicit construction of the bijection using the involutions $d$ and $d'$ defined in (14) and (15).

Let $\mathbf{v} = (p_1, \tau_1, \tau_2, \dots, \tau_{r-1}, \tau_r, p_2)$ be a two-pix-permutation of $[n]$ with $|p_1| = j$. If $p_2 \neq \emptyset$, then

$$ \mathbf{u} = (p_1, d(\tau_1), d(\tau_2), \dots, d(\tau_{r-1}), d(\tau_r), d'(p_2)), $$

otherwise,

$$ \mathbf{u} = (p_1, d(\tau_1), d(\tau_2), \dots, d(\tau_{r-1}), d'(\tau_r)). $$

As $d$ and $d'$ are involutions, this mapping is an involution on $W_n(j)$.

Since we have $\text{lec}(d(\tau_i)) = |\text{cont}(\tau_i)| - \text{lec}(\tau_i)$ for $1 \le i \le r$ and $\text{lec}(d'(p_2)) = |\text{cont}(p_2)| - 1$ in the case $p_2 \neq \emptyset$, it follows that $\text{lec}(\mathbf{u}) = \sum_{i=1}^r |\text{cont}(\tau_i)| + |\text{cont}(p_2)| - 1 - \text{lec}(\mathbf{v}) = n - j - 1 - \text{lec}(\mathbf{v})$. The above identity is also valid when $p_2 = \emptyset$.

Finally it follows from (19) that $(\text{inv} - \text{lec})\mathbf{u} = (\text{inv} - \text{lec})\mathbf{v}$. This finishes the proof of the lemma. $\square$

Combining Lemmas 2 and 3 we obtain a bijective proof of (7).

### 3 A new recurrence formula for the $(q, r)$-Eulerian polynomials

The Eulerian differential operator $\delta_x$ involved here is defined by

$$ \delta_x(f(x)) := \frac{f(x) - f(qx)}{x}, $$

for any $f(x) \in \mathbb{Q}[q][[x]]$ in the ring of formal power series in $x$ over $\mathbb{Q}[q]$ (instead of the traditional $(f(x) - f(qx))/(1 - q)x$, see [3]). A proof of Theorem 2 can be obtained by applying $\delta_z$ to both sides of (2), which is straightforward and is omitted.

**Remark 2** A different recurrence formula for $A_n(t, r, q)$ was obtained in [18, Corollary 4.3]. Eq. (10) is similar to two recurrence formulas in the literature: one for the $(\text{inv}, \text{des})$-q-Eulerian polynomials in [15, Corollary 2.22] (see also [3]) and the other one for the $(\text{maj}, \text{des})$-q-Eulerian polynomials in [15, Corollary 3.6].
We shall give another interpretation of $A_n(t, r, q)$ in the following.

Let $\pi \in \mathfrak{S}_n$. Recall that an inversion of $\pi$ is a pair $(\pi(i), \pi(j))$ such that $1 \le i < j \le n$ and $\pi(i) > \pi(j)$. An admissible inversion of $\pi$ is an inversion $(\pi(i), \pi(j))$ that satisfies either

* $1 < i$ and $\pi(i-1) < \pi(i)$ or

* there is some $l$ such that $i < l < j$ and $\pi(i) < \pi(l)$.

We write $\mathrm{ai}(\pi)$ the number of admissible inversions of $\pi$. Define the statistic $\mathrm{aid}(\pi) := \mathrm{ai}(\pi) + \mathrm{des}(\pi)$. For example, if $\pi = 42153$ then there are 5 inversions, but only (4, 3) and (5, 3) are admissible. So $\mathrm{inv}(\pi) = 5$, $\mathrm{ai}(\pi) = 2$ and $\mathrm{aid}(\pi) = 2+3=5$. The statistics $\mathrm{ai}$ and $\mathrm{aid}$ were first studied by Shareshian and Wachs [16] in the context of Poset Topology. Here we follow the definitions in [14]. The curious result that the pairs (aid, des) and (maj, exc) are equidistributed on $\mathfrak{S}_n$ was proved in [14] using techniques of Rees products and lexicographic shellability.

Let $\mathcal{W}$ be the set of all the words on $\mathbb{N}$. We define a new statistic, denoted by “rix”, on $\mathcal{W}$ recursively. Let $W = w_1w_2\cdots w_n$ be a word in $\mathcal{W}$ and $w_i$ be the rightmost maximum element of $W$. We define $\mathrm{rix}(W)$ by (with convention that $\mathrm{rix}(\emptyset) = 0$)

$$ \mathrm{rix}(W) := \begin{cases} 0, & \text{if } i = 1 \neq n, \\ 1 + \mathrm{rix}(w_1 \cdots w_{n-1}), & \text{if } i = n, \\ \mathrm{rix}(w_{i+1}w_{i+2} \cdots w_n), & \text{if } 1 < i < n. \end{cases} $$

For example, we have $\mathrm{rix}(1524335) = 1 + \mathrm{rix}(152433) = 1 + \mathrm{rix}(2433) = 1 + \mathrm{rix}(33) = 2 + \mathrm{rix}(3) = 3$. As every permutation can be viewed as a word on $\mathbb{N}$, this statistic is well-defined on permutations.

For $1 \le j \le n$, we write $\mathfrak{S}_n^{(j)}$ the set of permutations $\pi \in \mathfrak{S}_n$ with $\pi(j) = n$. We define

$$ B_n(t, r, q) := \sum_{\pi \in \mathfrak{S}_n} t^{\mathrm{des} \, \pi} r^{\mathrm{rix} \, \pi} q^{\mathrm{ai} \, \pi} $$

and its restricted version by

$$ B_n^{(j)}(t, r, q) := \sum_{\pi \in \mathfrak{S}_n^{(j)}} t^{\mathrm{des} \, \pi} r^{\mathrm{rix} \, \pi} q^{\mathrm{ai} \, \pi}. \qquad (21) $$

**Theorem 3** We have the following interpretation for $(q, r)$-Eulerian polynomials:

$$ A_n(t, r, q) = \sum_{\pi \in \mathfrak{S}_n} t^{\mathrm{des} \, \pi} r^{\mathrm{rix} \, \pi} q^{\mathrm{ai} \, \pi}. \qquad (22) $$

**Proof:** We will show that $B_n(t, r, q)$ satisfies the same recurrence formula and initial condition as $A_n(t, r, q)$. For $n \ge 1$, it is clear from the definition of $B_n(t, r, q)$ that

$$ B_{n+1}(t, r, q) = \sum_{1 \le j \le n+1} B_{n+1}^{(j)}(t, r, q). \qquad (23) $$
It is easy to see that

$$B_{n+1}^{(1)}(t, r, q) = tB_n(t, 1, q) \quad \text{and} \quad B_{n+1}^{(n+1)}(t, r, q) = rB_n(t, r, q). \qquad (24)$$

We then consider $B_{n+1}^{(j)}(t, r, q)$ for the case of $1 < j < n+1$.

For a set $X$, we denote by $\binom{X}{m}$ the $m$-element subsets of $X$ and $\mathfrak{S}_X$ the set of permutations of $X$. Let $W(n, j)$ be the set of all triples $(W, \pi_1, \pi_2)$ such that $W \in \binom{[n]}{j}$ and $\pi_1 \in \mathfrak{S}_W, \pi_2 \in \mathfrak{S}_{[n]\setminus W}$. It is not difficult to see that the mapping $\pi \mapsto (W, \pi_1, \pi_2)$ defined by

$$\bullet W = \{\pi(i) : 1 \le i \le j - 1\},$$

$$\bullet \pi_1 = \pi(1)\pi(2)\cdots\pi(j-1) \text{ and } \pi_2 = \pi(j+1)\pi(j+2)\cdots\pi(n)$$

is a bijection between $\mathfrak{S}_n^{(j)}$ and $W(n-1, j-1)$ and satisfies

$$\mathrm{des}(\pi) = \mathrm{des}(\pi_1) + \mathrm{des}(\pi_2) + 1, \quad \mathrm{rix}(\pi) = \mathrm{rix}(\pi_2)$$

and

$$\mathrm{ai}(\pi) = \mathrm{ai}(\pi_1) + \mathrm{ai}(\pi_2) + \mathrm{inv}(W, [n-1] \setminus W) + n - j.$$

Thus, for $1 < j < n+1$, we have

$$\begin{align*}
B_{n+1}^{(j)}(t, r, q) &= \sum_{\pi \in \mathfrak{S}_{n+1}^{(j)}} t^{\mathrm{des}\pi} r^{\mathrm{rix}\pi} q^{\mathrm{ai}\pi} \\
&= tq^{n+1-j} \sum_{(W, \pi_1, \pi_2) \in W(n, j-1)} q^{\mathrm{inv}(W, [n] \setminus W)} q^{\mathrm{ai}(\pi_1)} t^{\mathrm{des}(\pi_1)} r^{\mathrm{rix}(\pi_2)} q^{\mathrm{ai}(\pi_2)} t^{\mathrm{des}(\pi_2)} \\
&= tq^{n+1-j} \sum_{W \in \binom{[n]}{j-1}} q^{\mathrm{inv}(W, [n] \setminus W)} \sum_{\pi \in \mathfrak{S}_W} q^{\mathrm{ai}(\pi_1)} t^{\mathrm{des}(\pi_1)} \sum_{\pi_2 \in \mathfrak{S}_{[n] \setminus W}} r^{\mathrm{rix}(\pi_2)} q^{\mathrm{ai}(\pi_2)} t^{\mathrm{des}(\pi_2)} \\
&= tq^{n+1-j} \left[ \begin{smallmatrix} n \\ j-1 \end{smallmatrix} \right]_q B_{j-1}(t, 1, q) B_{n+1-j}(t, r, q), \tag{25}
\end{align*}$$

where we apply (13) to the last equality. Substituting (24) and (25) into (23) we obtain

$$B_{n+1}(t, r, q) = rB_n(t, r, q) + tB_n(t, 1, q) + t \sum_{j=1}^{n-1} \begin{bmatrix} n \\ j \end{bmatrix}_q q^j B_j(t, r, q) B_{n-j}(t, 1, q).$$

By Theorem 2, $B_n(t, r, q)$ and $A_n(t, r, q)$ satisfy the same recurrence formula and initial condition, thus $B_n(t, r, q) = A_n(t, r, q)$. This finishes the proof of the theorem. $\square$

**Corollary 2** The three triplets (rix, des, aid), (fix, exc, maj) and (pix, lec, inv) are equidistributed on $\mathfrak{S}_n$.

**Remark 3** At the Permutation Patterns 2012 conference, Alexander Burstein [1] gave a direct bijection on $\mathfrak{S}_n$ that transforms the triple (rix, des, aid) to (pix, lec, inv). The new statistic “rix” was introduced independently therein under the name “aix”. Actually, the definitions of both are slightly different, but they are the same up to an easy transformation. It would be very interesting to find a similar bijective proof of the equidistribution of (rix, des, aid) and (fix, exc, maj).
# 4 A symmetrical identity for restricted q-Eulerian polynomials

## 4.1 An interpretation of $B_{n,k}^{(j)}(q)$ and a proof of Theorem 1

It follows from (2) and (8) that $B_{1,0}^{(1)}(q) = 1$ and $B_{n,k}^{(1)}(q) = A_{n-1,k-1}(q)$ for $n \ge 2$. For $2 \le j \le n$, we have the following interpretation for $B_{n,k}^{(j)}(q)$, which shows that $B_{n,k}^{(j)}(q)$ is really a q-analogue of the restricted Eulerian number studied in [4] and defined to be the number of permutations in $S_n^{(j)}$ with $k$ descents.

**Lemma 4** For $2 \le j \le n$, $B_{n,k}^{(j)}(q) = \sum_{\substack{\pi \in S_n^{(j)} \\ \mathrm{des}(\pi) = k}} q^{ai(\pi)+2j-n-1}$.

**Proof:** When $j \ge 2$, by the recurrence relation (25), one can compute without difficulty that the exponential generating function $\sum_{n \ge j} q^{2j-n-1} B_n^{(j)}(t, 1, q) \frac{z^{n-1}}{(q;q)_{n-1}}$ is exactly the right side of (8) using (2) and (22), which would finish the proof of the lemma. $\square$

**Lemma 5** For $1 < j < n$, we have

$$B_{n,k}^{(j)}(q) = B_{n,n-1-k}^{(j)}(q).$$

**Proof:** We first construct an involution $f: \pi \mapsto \pi'$ on $S_n$ satisfying

$$\mathrm{ai}(\pi) = \mathrm{ai}(\pi') \quad \text{and} \quad \mathrm{des}(\pi) = n - 1 - \mathrm{des}(\pi'). \qquad (26)$$

For $n=1$, define $f(\mathrm{id}) = \mathrm{id}$. For $n \ge 2$, suppose that $\pi = \pi_1 \cdots \pi_n$ is a permutation of $\{\pi_1, \cdots, \pi_n\}$ and $\pi_j$ is the maximum element in $\{\pi_1, \cdots, \pi_n\}$. We construct $f$ recursively as follows

$$f(\pi) = \begin{cases} f(\pi_2\pi_3\cdots\pi_n)\pi_1, & \text{if } j=1, \\ \pi_n f(\pi_1\pi_2\cdots\pi_{n-1}), & \text{if } j=n, \\ f(\pi_1\pi_2\cdots\pi_{j-1})\pi_j f(\pi_{j+1}\pi_{j+2}\cdots\pi_n), & \text{otherwise.} \end{cases}$$

For example, if $\pi = 3257641$, then $f(\pi) = f(325)7f(641) = 5f(32)7f(41)6 = 5237146$. Clearly, $\mathrm{ai}(\pi) = 7 = \mathrm{ai}(\pi')$ and $\mathrm{des}(\pi) = 4 = 7 - 1 - \mathrm{des}(\pi')$. It is not difficult to see that $f$ is an involution. We can show that $f$ satisfies (26) by induction on $n$, which is routine and left to the reader.

For each $\pi = \pi_1 \cdots \pi_{j-1} n \pi_{j+1} \cdots \pi_n$ in $S_n^{(j)}$, we then define $g(\pi) = f(\pi_1 \cdots \pi_{j-1}) n f(\pi_{j+1} \cdots \pi_n)$. As $f$ is an involution, $g$ is an involution on $S_n^{(j)}$. It follows from (26) that $\mathrm{ai}(g(\pi)) = \mathrm{ai}(\pi)$ and $\mathrm{des}(\pi) = n - 1 - \mathrm{des}(g(\pi))$, which completes the proof in view of Lemma 4. $\square$

**Remark 4** Supposing that $\pi = \pi_1 \cdots \pi_n$ is a permutation of $\{\pi_1, \cdots, \pi_n\}$ and $\pi_j$ is the maximum element in $\{\pi_1, \cdots, \pi_n\}$, we modify $f$ to $f'$ as follows:

$$f'(\pi) = \begin{cases} f'(\pi_2\pi_3\cdots\pi_n)\pi_1, & \text{if } j=1, \\ \pi, & \text{if } j=n, \\ f'(\pi_1\pi_2\cdots\pi_{j-1})\pi_j f'(\pi_{j+1}\pi_{j+2}\cdots\pi_n), & \text{otherwise.} \end{cases}$$

The reader is invited to check that $f'$ would provide another bijective proof of Corollary 1 using $(\mathrm{des}, \mathrm{rix}, \mathrm{ai})$.

Through some similar analytical arguments as [4, Theorem 2] starting with the generating function (8) and using Lemma 4 and 5 we can get a proof of Theorem 1. The details are omitted.
## 4.2 Another interpretation of $B_{n,k}^{(j)}(q)$ and a bijective proof of Theorem 1

Let $\tilde{\mathfrak{S}}_n^{(j)} := \{\pi \in \mathfrak{S}_n : \pi(j+1) = 1\}$ for $1 \le j < n$ and $\tilde{\mathfrak{S}}_n^{(n)} := \{\pi' \square 1 : \pi' \in \mathfrak{S}_{[n]\setminus\{1\}}\}$. The “□” in $\pi = \pi_1\pi_2\cdots\pi_{n-1}\square 1 \in \tilde{\mathfrak{S}}_n^{(n)}$ means that the n-th position of $\pi$ is empty and the hook factorization of $\pi$ is defined to be $p\tau_1 \cdots \tau_r \square 1$, where $p\tau_1 \cdots \tau_r$ is the hook factorization of $\pi_1 \cdots \pi_{n-1}$ and “□1” is viewed as a hook. We also define $\text{lec}(\pi_1\pi_2\cdots\pi_{n-1}\square 1) = \sum_{i=1}^r \text{lec}(\tau_i)$ and $\text{inv}(\pi_1\pi_2\cdots\pi_{n-1}\square 1) = \text{inv}(\pi_1\pi_2\cdots\pi_{n-1}1)$. For example, $\tilde{\mathfrak{S}}_3^{(3)} = \{32\square 1, 23\square 1\}$ with $\text{lec}(32\square 1) = 1, \text{lec}(23\square 1) = 0$ and $\text{inv}(32\square 1) = 3, \text{inv}(23\square 1) = 2$.

**Lemma 6** Let $B_{n,k}^{(j)}(q)$ be defined by (8). Then $B_{n,k}^{(j)}(q) = \sum_{\substack{\pi \in \tilde{\mathfrak{S}}_n^{(j)} \\ \text{lec}(\pi)=k}} q^{(\text{inv-lec})\pi}$.

**Proof:** Let $\bar{B}_n^{(j)}(t, q) := \sum_{\pi \in \tilde{\mathfrak{S}}_n^{(j)}} q^{(\text{inv-lec})\pi} t^{\text{lec}\pi}$. We recall that, to derive the hook factorization of a permutation, one can start from the right and factor out each hook step by step. Therefore, the hook factorization of $\pi = \pi_1 \cdots \pi_{j-1} \pi_j 1 \pi_{j+2} \cdots \pi_n$ in $\pi \in \tilde{\mathfrak{S}}_n^{(j)}$ is $p\tau_1 \cdots \tau_s \tau'_1 \cdots \tau'_r$, where $p\tau_1 \cdots \tau_s$ and $\tau'_1 \cdots \tau'_r$ are hook factorizations of $\pi_1 \cdots \pi_{j-1}$ and $\pi_j 1 \pi_{j+2} \cdots \pi_n$, respectively. When $n > j$, it is not difficult to see that

$$ \text{lec}(\pi_j 1 \pi_{j+2} \cdots \pi_n) = 1 + \text{lec}(\pi_j \pi_{j+2} \cdots \pi_n) $$

and

$$ (\text{inv} - \text{lec})(\pi_j 1 \pi_{j+2} \cdots \pi_n) = (\text{inv} - \text{lec})(\pi_j \pi_{j+2} \cdots \pi_n). $$

Thus by (13), we have

$$ \bar{B}_n^{(j)}(t, q) = A_{j-1}(t, q) q^{j-1} \begin{bmatrix} n-1 \\ j-1 \end{bmatrix}_q t A_{n-j}(t, q) \quad (27) $$

for $n > j$. Clearly, $\bar{B}_j^{(j)}(t, q) = A_{j-1}(t, q)q^{j-1}$. So by (2), the exponential generating function $\sum_{n \ge j} \bar{B}_n^{(j)}(t, q) \frac{z^{n-1}}{(q;q)_{n-1}}$ is the right side of (8). This finishes the proof of the lemma. $\square$

**Remark 5** This interpretation can also be deduced directly from the interpretation in Lemma 4 using Burstein's bijection [1].

For $X \subset [n]$ with $|X| = m$ and $1 \in X$, we can define $\tilde{\mathfrak{S}}_X^{(j)}$ for $1 \le j \le m$ similarly as $\tilde{\mathfrak{S}}_m^{(j)}$ like this:

$$ \tilde{\mathfrak{S}}_X^{(j)} := \{\pi \in \mathfrak{S}_X : \pi(j+1) = 1\} \text{ for } 1 \le j < m \text{ and } \tilde{\mathfrak{S}}_X^{(m)} := \{\pi' \square 1 : \pi' \in \mathfrak{S}_{X \setminus \{1\}}\}. $$

For $1 \le j \le n$, we define a $j$-restricted two-pix-permutation of $[n]$ to be a pair $\mathbf{v} = (\pi, p_2)$ such that $p_2$ (possibly empty) is an increasing words on $[n]$ and $\pi \in \tilde{\mathfrak{S}}_X^{(j)}$ with $X = [n] \setminus \{\text{cont}(p_2)\}$. Similarly, we define $\text{lec}(\mathbf{v}) = \text{lec}(\pi)$ and $\text{inv}(\mathbf{v}) = \text{inv}(\pi) + \text{inv}(\text{cont}(\pi), \text{cont}(p_2))$. Let $W_n^{(j)}$ denote the set of all $j$-restricted two-pix-permutations of $[n]$.

**Lemma 7** Let $a, j$ be positive integers. Then

$$ \sum_{\substack{\mathbf{v} \in W_n^{(j)} \\ \text{lec}\mathbf{v}=a}} q^{(\text{inv-lec})\mathbf{v}} = \sum_{k \ge 1} \begin{bmatrix} n-1 \\ k-1 \end{bmatrix}_q B_{k,a}^{(j)}(q). \quad (28) $$
**Proof:** It follows from Lemma 6 and some similar arguments as in the proof of Lemma 2. □

**Lemma 8** Let $2 \le j \le n$. Then there is an involution $v \mapsto u$ on $W_n^{(j)}$ satisfying

$$ \mathrm{lec}(\mathbf{v}) = n - 2 - \mathrm{lec}(\mathbf{u}), \quad \text{and} \quad (\mathrm{inv} - \mathrm{lec})\mathbf{v} = (\mathrm{inv} - \mathrm{lec})\mathbf{u}. \qquad (29) $$

**Proof:** Suppose $v = (\pi, p_2) \in W_n^{(j)}$ and $\pi = \tau_0\tau_1 \cdots \tau_r$ is the hook factorization of $\pi$ such that $\tau_0$ is a hook or an increasing word and $\tau_i$ ($1 \le i \le r$) are hooks. We also assume that $p_2 = x_1 \cdots x_l$ if $p_2$ is not empty. Note that $1 \notin \mathrm{cont}(\tau_0)$ since $j \ne 1$. We will use the involutions $d$ and $d'$ defined in (14) and (15). There are several cases to be considered:

(i) $\tau_r = \square 1$. Then

$$ \mathbf{u} = \begin{cases} (d'(\tau_0)d(\tau_1)\cdots d(\tau_{r-1})x_l 1 x_1 x_2 \cdots x_{l-1}, \emptyset), & \text{if } p_2 \neq \emptyset; \\ (d'(\tau_0)d(\tau_1)\cdots d(\tau_{r-1})\square 1, \emptyset), & \text{otherwise.} \end{cases} $$

(ii) $\tau_r = y_s 1 y_1 \cdots y_{s-1}$. Then

$$ \mathbf{u} = \begin{cases} (d'(\tau_0)d(\tau_1)\cdots d(\tau_{r-1})d(\tau_r)d'(p_2), \emptyset), & \text{if } p_2 \neq \emptyset; \\ (d'(\tau_0)d(\tau_1)\cdots d(\tau_{r-1})\square 1, y_1 \cdots y_s), & \text{if } p_2 = \emptyset \text{ and } y_s > y_{s-1}; \\ (d'(\tau_0)d(\tau_1)\cdots d(\tau_{r-1})d'(\tau_r), \emptyset), & \text{otherwise.} \end{cases} $$

(iii) $1 \notin \mathrm{cont}(\tau_r)$. Then

$$ \mathbf{u} = \begin{cases} (d'(\tau_0)d(\tau_1)\cdots d(\tau_{r-1})d(\tau_r)d'(p_2), \emptyset), & \text{if } p_2 \neq \emptyset; \\ (d'(\tau_0)d(\tau_1)\cdots d(\tau_{r-1}), d'(\tau_r)), & \text{if } p_2 = \emptyset \text{ and } \mathrm{lec}(\tau_r) = |\tau_r| - 1; \\ (d'(\tau_0)d(\tau_1)\cdots d(\tau_{r-1})d'(\tau_r), \emptyset), & \text{otherwise.} \end{cases} $$

First of all, one can check that $\mathbf{u} \in W_n^{(j)}$. Secondly, as $d, d'$ are involutions, the above mapping is an involution. Finally, this involution satisfies (29) in all cases. This completes the proof of the lemma. □

Combining Lemmas 7 and 8 we obtain a bijective proof of Theorem 1.

## Acknowledgements

The author would like to thank Prof. Jiang Zeng for useful conversations and an anonymous referee for carefully reading the manuscript.

## References

[1] A. Burstein, A combinatorial proof of joint equidistribution of some pairs of permutation statistics, talk at Permutation Patterns 2012.
[2] L. Carlitz, A combinatorial property of $q$-Eulerian numbers, Amer. Math. Monthly, **82** (1975), 51–54.

[3] C.-O. Chow, A recurrence relation for “inv” analogue of $q$-Eulerian polynomials, Electron. J. Combin., **17** (2010), #N22.

[4] F. Chung and R. Graham, Generalized Eulerian Sums, J. Comb., **3** (2012), 299–316.

[5] F. Chung, R. Graham, D. Knuth, A symmetrical Eulerian identity, J. Comb., **1** (2010), 29–38.

[6] R.J. Clarke, E. Steingrímsson, and J. Zeng, New Euler-Mahonian statistics on permutations and words, Adv. in Appl. Math., **18** (1997), 237–270.

[7] D. Foata, Eulerian polynomials: from Euler's time to the present, The Legacy of Alladi Ramakrishnan in the Mathematical Sciences (2010), 253–273.

[8] D. Foata and G.-N. Han, The $q$-Tangent and $q$-Secant numbers via basic Eulerian polynomials, Proc. Amer. Math. Soc, **138** (2009), 385–393.

[9] D. Foata and G.-N. Han, Fix-mahonian calculus III; a quardruple distribution, Monatsh. Math., **154** (2009), 29–52.

[10] D. Foata and G.-N. Han, Decreases and descents in words, Sem. Lothar. Combin., **B58a** (2007), 17 pp.

[11] D. Foata and G.-N. Han, The decrease value theorem with an application to permutation statistics, Adv. in Appl. Math., **46** (2011), 296–311.

[12] I.M. Gessel, A coloring problem, Amer. Math. monthly, **98** (1991), 530–533.

[13] G.-N. Han, Z. Lin and J. Zeng, A symmetrical $q$-Eulerian identity, Sem. Lothar. Combin., B67c (2012), 11 pp.

[14] S. Linusson, J. Shareshian and M.L. Wachs, Rees products and lexicographic shellability, J. Comb., **3** (2012), 243–276.

[15] S. Park, The $r$-Multipermutations, J. Combin. Theory Ser. A, **67** (1994), 44–71.

[16] J. Shareshian and M.L. Wachs, $q$-Eulerian polynomials: Excedance Number and Major Index, Electron. Res. Announc. Amer. Math. Soc. **13** (2007), 33–45.

[17] J. Shareshian and M.L. Wachs, Poset homology of Rees products, and $q$-Eulerian polynomials, Electron. J. Combin., **16** (2009), #R20.

[18] J. Shareshian and M.L. Wachs, Eulerian quasisymmetric function, Adv. in Math., **225** (2011), 2921–2966.

[19] R.P. Stanley, *Enumerative combinatorics*, Vol. 1, Cambridge University Press, Cambridge, 1997.

[20] R.P. Stanley, Binomial posets, Möbius inversion, and permutation enumeration, J. Combin. Theory Ser. A, **20** (1976), 336–356.

[21] M.L. Wachs, On $q$-derangement numbers, Proc. Amer. Math. Soc., **106** (1989), 273–278.