# Eulerian polynomials and excedance statistics via continued fractions

Bin Han, Jianxi Mao, Jiang Zeng

► To cite this version:

Bin Han, Jianxi Mao, Jiang Zeng. Eulerian polynomials and excedance statistics via continued fractions. Seminaire Lotharingien de Combinatoire, 2020, 84 (84B), Article #40, 12 pp. hal-04770465

HAL Id: hal-04770465

https://hal.science/hal-04770465v1

Submitted on 7 Nov 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>
# Eulerian polynomials and excedance statistics via continued fractions

Bin Han*¹, Jianxi Mao†², and Jiang Zeng‡³

¹Department of Mathematics, Bar-Ilan University, Ramat-Gan, Israel.

²School of Mathematic Sciences, Dalian University of Technology, Dalian, China

³Univ Lyon, Université Claude Bernard Lyon 1, CNRS, Institut Camille Jordan, Villeurbanne, France

**Abstract.** It is well known that the permutation peak polynomials and descent polynomials are connected via a quadratic transformation. By rephrasing the latter formula with permutation cycle peaks and excedances we are able to prove a series of general formulas expressing polynomials counting permutations by various excedance statistics in terms of refined Eulerian polynomials.

**Résumé.** Il est bien connu que les polynômes de pic de permutations et les polynômes de descente sont connectés via une transformation quadratic. En reformulant cette dernière formule avec les pics de cycle et les excédances du cycle de permutation, nous pouvons prouver une série de formules générales exprimant des polynômes énuméra-tives des permutations par diverses statistiques d'excédance en termes de polynômes eulériens raffinés.

**Keywords:** Eulerian polynomials, peak polynomials, Gamma-positivity, q-Narayana polynomials, continued fractions, Laguerre histories, Françon-Viennot bijection, Foata-Zeilberger bijection.

## 1 Introduction

The Eulerian polynomials $A_n(t)$ can be defined through the continued fraction expansion [16]

$$ \sum_{n \ge 0} A_n(t) z^n = 1/1 - 1 \cdot z/1 - t \cdot z/1 - 2 \cdot z/1 - 2t \cdot z/1 - 3 \cdot z/1 - 3t \cdot z/1 - \dots \quad (1.1) $$

<footnote>*han@math.biu.ac.il. Partially supported by the Israel Science Foundation, grant no. 1970/18 and by the China Scholarship Council.</footnote>

<footnote>†maojianxi@hotmail.com. Supported by the China Scholarship Council.</footnote>

<footnote>‡zeng@math.univ-lyon1.fr.</footnote>
For an $n$-permutation $\sigma := \sigma(1)\sigma(2)\cdots\sigma(n)$ of the word $1\dots n$, an index $i$ ($1 \le i \le n-1$) is a descent (resp. excedance) of $\sigma$ if $\sigma(i) > \sigma(i+1)$ (resp. $\sigma(i) > i$). It is well-known [7, 13] that

$$A_n(t) = \sum_{\sigma \in \mathfrak{S}_n} t^{\text{des}\sigma} = \sum_{\sigma \in \mathfrak{S}_n} t^{\text{exc}\sigma}, \qquad (1.2)$$

where $\mathfrak{S}_n$ is the set of $n$-permutations and des$\sigma$ (resp. exc$\sigma$) denotes the number of descents (resp. excedances) of $\sigma$. The value $\sigma(i)$ ($2 \le i \le n-1$) is a peak of $\sigma$ if $\sigma(i-1) < \sigma(i) > \sigma(i+1)$ and the peak polynomials are defined by

$$P_n^{\text{pk}}(x) := \sum_{\sigma \in \mathfrak{S}_n} x^{\text{pk}'\sigma} \qquad (1.3)$$

where $\text{pk}'\sigma$ denotes the number of peaks of $\sigma$. The peak polynomials are related to the Eulerian polynomials by Stembridge's identity, see [2, 18].

$$A_n(t) = \left(\frac{1+t}{2}\right)^{n-1} P_n^{\text{pk}}\left(\frac{4t}{(1+t)^2}\right), \qquad (1.4)$$

which can be used to compute the peak polynomials. Obviously (1.4) is equivalent to the so-called $\gamma$-expansion of Eulerian polynomials

$$A_n(t) = \sum_{k=0}^{\lfloor (n-1)/2 \rfloor} 2^{2k+1-n} \gamma_{n,k} t^k (1+t)^{n-1-2k}, \qquad (1.5)$$

where $\gamma_{n,k}$ is the number of $n$-permutations with $k$ peaks. In the form of (1.5) it is not difficult to see that Stembridge's formula (1.4) is actually equivalent to a formula of Foata and Schüzenberger [7, Théorème 5.6] via Brändén's modified Foata-Strehl action (cf. [2]). In the last two decades, many people studied the refinements of Stembridge's identity, see Brändén [2], Shin and Zeng [14, 15], Zhuang [18], Athanasiadis [1] and the references therein. In particular, Zhuang [18] has proved several identities expressing polynomials counting permutations by various descent statistics in terms of Eulerian polynomials, extending results of Stembridge, Petersen, and Brändén.

In this paper we shall prove generalizations of Stembridge's formula using excedance statistics by further exploiting the continued fraction technique in [14, 15]. Our main tool is the combinatorial theory of continued fractions due to Flajolet [6] and bijections due to Françon-Viennot, Foata-Zeilberger between permutations and *Laguarre histories*, see [9, 8, 6, 4]. As in [14] this approach uses both linear and cycle statistics on permutations.

This extended abstract is a summary of the recent paper [11]. In Section 2 we introduce the work in [14, 15], and construct a bijection $\psi$, which is an analogue of Foata-Zeilberger's bijection from $\mathfrak{S}_{n+1}$ to $\mathcal{L}\mathcal{H}_n$. In Section 3 we present two analogues of (1.4) using excedance statistics for permutations.
# 2 Background and preliminaries

## 2.1 Permutation statistics and two bijections

For $\sigma = \sigma(1)\sigma(2)\cdots\sigma(n) \in \mathfrak{S}_n$ with convention 0-0, i.e., $\sigma(0) = \sigma(n+1) = 0$, a value $\sigma(i)$ ($1 \le i \le n$) is called

* a peak if $\sigma(i-1) < \sigma(i)$ and $\sigma(i) > \sigma(i+1)$;

* a valley if $\sigma(i-1) > \sigma(i)$ and $\sigma(i) < \sigma(i+1)$;

* a double ascent if $\sigma(i-1) < \sigma(i)$ and $\sigma(i) < \sigma(i+1)$;

* a double descent if $\sigma(i-1) > \sigma(i)$ and $\sigma(i) > \sigma(i+1)$.

The set of Peaks (resp. Valleys, double ascents, double descents) of $\sigma$ is denoted by

$$ \mathrm{Pk}\sigma \quad (\mathrm{resp.} \ \mathrm{Val}\sigma, \ \mathrm{Da}\sigma, \ \mathrm{Dd}\sigma). $$

Let $\mathrm{pk}\sigma$ (resp. $\mathrm{val}\sigma$, $\mathrm{da}\sigma$, $\mathrm{dd}\sigma$) be the number of peaks (resp. valleys, double ascents, double descents) of $\sigma$. For $i \in [n] := \{1, \dots, n\}$, we introduce the following statistics:

$$ \begin{aligned} (31-2)_i \sigma &= \#\{j: 1 < j < i \text{ and } \sigma(j) < \sigma(i) < \sigma(j-1)\} \\ (2-31)_i \sigma &= \#\{j: i < j < n \text{ and } \sigma(j+1) < \sigma(i) < \sigma(j)\} \\ (2-13)_i \sigma &= \#\{j: i < j < n \text{ and } \sigma(j) < \sigma(i) < \sigma(j+1)\} \\ (13-2)_i \sigma &= \#\{j: 1 < j < i \text{ and } \sigma(j-1) < \sigma(i) < \sigma(j)\} \end{aligned} \quad (2.1) $$

and define (see (2.33)):

$$ (31-2) = \sum_{i=1}^{n} (31-2)_i, \quad (2-31) = \sum_{i=1}^{n} (2-31)_i, \quad (2-13) = \sum_{i=1}^{n} (2-13)_i, \quad (13-2) = \sum_{i=1}^{n} (13-2)_i. $$

Now, we consider $\sigma \in \mathfrak{S}_n$ as a bijection $i \mapsto \sigma(i)$ for $i \in [n]$, a value $x = \sigma(i)$ is called a cyclic peak if $i = \sigma^{-1}(x) < x$ and $x > \sigma(x)$; a cyclic valley if $i = \sigma^{-1}(x) > x$ and $x < \sigma(x)$; a double excedance if $i = \sigma^{-1}(x) < x$ and $x < \sigma(x)$; a double drop if $i = \sigma^{-1}(x) > x$ and $x > \sigma(x)$; a fixed point if $x = \sigma(x)$. We say that $i \in [n-1]$ is an ascent of $\sigma$ if $\sigma(i) < \sigma(i+1)$ and that $i \in [n]$ is a drop of $\sigma$ if $\sigma(i) < i$. Let Cpk (resp. Cval, Cda, Cdd, Fix, Asc, Drop) be the set of cyclic peaks (resp. cyclic valleys, double excedances, double drops, fixed points, ascents, drops) and denote the corresponding cardinality by cpk (resp. cval, cda, cdd, fix, asc, drop). Moreover, define

$$ \mathrm{cros}_i \sigma = \#\{j: j < i < \sigma(j) < \sigma(i) \text{ or } \sigma(i) < \sigma(j) \le i < j\}, \quad (2.2) $$

$$ \mathrm{nest}_i \sigma = \#\{j: j < i < \sigma(i) < \sigma(j) \text{ or } \sigma(j) < \sigma(i) \le i < j\}. \quad (2.3) $$
Let cros<fnref n="1" /> = Σn i=1 crosᵢ and icr σ = cros σ⁻<fnref n="1" />. Define nest = Σn i=1 nestᵢ. Note (cf. [10, Remark 2.4]) that

$$ \text{nest} \sigma^{-1} = \text{nest} \sigma \quad \text{for} \quad \sigma \in \mathfrak{S}_n. \qquad (2.4) $$

A pair of integers (i, j) is an inversion of σ ∈ Sₙ if i < j and σ(i) > σ(j), and σ(i) (resp. σ(j)) is called inversion top (resp. bottom). Let inv σ be the inversion number of σ.

For σ ∈ Sₙ with convention 0–∞, i.e., σ(0) = 0 and σ(n + 1) = ∞, let Lpk (resp. Lval, Lda, Ldd) be the set of peaks (resp. valleys, double ascents and double decents) and denote the corresponding cardinality by lpk (resp. lval, lda and ldd). For i ∈ [n], the value σ(i) is called a left-to-right maximum if σ(i) = max {σ(1), σ(2), ..., σ(i)} A double ascent σ(i) (i = 1, ..., n) is called a foremaximum of σ if it is at the same time a left-to-right maximum Denote the number of foremaxima of σ by fmax σ. Note that for the peak number pk' in (1.3) we have following identities :

$$ \text{pk}' = \text{val} = \text{pk} - 1 \quad \text{and} \quad \text{lval} = \text{lpk}. \qquad (2.5) $$

Now we recall two bijections Φ and Ψ due to Clarke et al. [4] and Shin-Zeng [14], respectively.

## 2.2 The bijection Φ

Let σ = σ(1) ... σ(n) ∈ Sₙ, an inversion top number (resp. inversion bottom number) of a letter x := σ(i) in the word σ is the number of occurrences of inversions of form (i, j) (resp (j, i)). A letter σ(i) is a descent top (resp. descent bottom) if σ(i) > σ(i + 1) (resp. σ(i − 1) > σ(i)). Given a permutation σ, we first construct two biwords, (f' f) and (g' g), where f (resp. g) is the subword of descent bottoms (resp. nondescent bottoms) in σ ordered increasingly, and f' (resp. g') is the permutation of descent tops (resp. nondescent tops) in σ such that the inversion bottom (resp. top) number of each letter x := σ(i) in f' (resp. g') is (2-31)ₓσ, and then form the biword w = (f' g' g) by concatenating f and g, and f' and g', respectively.

Rearranging the columns of w, so that the bottom row is in increasing order, we obtain the permutation τ = Φ(σ) as the top row of the rearranged bi-word.

The following result can be found in [14, Theorem 12] and its proof.

**Lemma 2.1** (Shin-Zeng). For σ ∈ Sₙ, we have

$$ \begin{align} & (2-31, 31-2, \text{des}, \text{asc}, \text{lda} - \text{fmax}, \text{ldd}, \text{lval}, \text{lpk}, \text{fmax})\sigma \nonumber \\ &= (\text{nest}, \text{icr}, \text{drop}, \text{exc} + \text{fix}, \text{cda}, \text{cdd}, \text{cval}, \text{cpk}, \text{fix})\Phi(\sigma) \tag{2.6} \\ &= (\text{nest}, \text{cros}, \text{exc}, \text{drop} + \text{fix}, \text{cdd}, \text{cda}, \text{cval}, \text{cpk}, \text{fix})(\Phi(\sigma))^{-1}, \nonumber \end{align} $$

<footnote n="1">¹Our definition of cros corresponds to icr in [10].</footnote>
$$ (\mathrm{Lval}, \mathrm{Lpk}, \mathrm{Lda}, \mathrm{Ldd})\sigma = (\mathrm{Cval}, \mathrm{Cpk}, \mathrm{Cda} \cup \mathrm{Fix}, \mathrm{Cdd})\Phi(\sigma), \quad (2.7) $$

$$ (2-31)_i\sigma = \mathrm{nest}_i\Phi(\sigma) \quad \forall i = 1, \dots, n. \quad (2.8) $$

## 2.3 The bijection Ψ

Given a permutation $\sigma \in \mathfrak{S}_n$, let

$$ \hat{\sigma} = \begin{pmatrix} 1 & 2 & \dots & n & n+1 \\ \sigma(1)+1 & \sigma(2)+1 & \dots & \sigma(n)+1 & 1 \end{pmatrix}, \quad (2.9) $$

and $\tau := \Phi(\hat{\sigma}) \in \mathfrak{S}_{n+1}$. Since the last element of $\hat{\sigma}$ is 1, the first element of $\tau$ should be $n+1$. Define the bijection $\Psi: \mathfrak{S}_n \to \mathfrak{S}_n$ by

$$ \Psi(\sigma) := \tau(2) \dots \tau(n+1) \in \mathfrak{S}_n. \quad (2.10) $$

## 2.4 The star variation

For $\sigma = \sigma(1) \dots \sigma(n) \in \mathfrak{S}_n$, we define its star compagnon $\sigma^*$ as a permutation of $\{0, \dots, n\}$ by

$$ \sigma^* = \begin{pmatrix} 0 & 1 & 2 & \dots & n \\ n & \sigma(1)-1 & \sigma(2)-1 & \dots & \sigma(n)-1 \end{pmatrix}. \quad (2.11) $$

We define the following sets of cyclic star statistics for $\sigma$:

$$ \mathrm{Cpk}^* \sigma = \{i \in [n-1] : (\sigma^*)^{-1}(i) < i > \sigma^*(i)\}, \quad (2.12) $$

$$ \mathrm{Cval}^* \sigma = \{i \in [n-1] : (\sigma^*)^{-1}(i) > i < \sigma^*(i)\}, \quad (2.13) $$

$$ \mathrm{Cda}^* \sigma = \{i \in [n-1] : (\sigma^*)^{-1}(i) < i < \sigma^*(i)\}, \quad (2.14) $$

$$ \mathrm{Cdd}^* \sigma = \{i \in [n-1] : (\sigma^*)^{-1}(i) > i > \sigma^*(i)\}, \quad (2.15) $$

$$ \mathrm{Fix}^* \sigma = \{i \in [n-1] : i = \sigma^*(i)\}, \quad (2.16) $$

$$ \mathrm{Wex}^* \sigma = \{i \in [n-1] : i \le \sigma^*(i)\} (= \mathrm{exc} \sigma), \quad (2.17) $$

$$ \mathrm{Drop}^* \sigma = \{i \in [n] : i > \sigma^*(i)\}. \quad (2.18) $$

The corresponding cardinalties are denoted by $\mathrm{cpk}^*$, $\mathrm{cval}^*$, $\mathrm{cda}^*$, $\mathrm{cdd}^*$, $\mathrm{fix}^*$, $\mathrm{wex}^*$ and $\mathrm{drop}^*$, respectively.

By (2.12), (2.15) and (2.18), we have $\mathrm{drop}^* - 1 = \mathrm{cdd}^* + \mathrm{cpk}^*$.

**Theorem 2.2.** For $\sigma \in \mathfrak{S}_n$, we have

$$ (\mathrm{Val}, \mathrm{Pk} \setminus \{n\}, \mathrm{Da}, \mathrm{Dd})\sigma = (\mathrm{Cval}^*, \mathrm{Cpk}^*, \mathrm{Cda}^* \cup \mathrm{Fix}^*, \mathrm{Cdd}^*)\Psi(\sigma) \quad (2.19) $$

and

$$ ((2-13)_i, (31-2)_i)\sigma = (\mathrm{nest}_i, \mathrm{cros}_i)\Psi(\sigma) \quad \text{for } i \in [n]. \quad (2.20) $$
Since $asc = val + da$, $des = pk + dd - 1$, $wex^* = cval^* + cda^* + fix^*$, $drop^* - 1 = cdd^* + cpk^*$, we get the following result in [14, Theorem 12].

**Corollary 2.3 (Shin-Zeng).** For $\sigma \in \mathcal{S}_n$ we have

$$ (2-13, 31-2, des, asc, da, dd, val)\sigma \\ = (nest, cros, drop^* - 1, wex^*, cda^* + fix^*, cdd^*, cval^*)\Psi(\sigma). \quad (2.21) $$

## 2.5 Laguerre histories as permutation encodings

A 2-Motzkin path of length $n$ is a word $\mathbf{s} := s_1 \dots s_n$ on the alphabet $\{U, D, L_r, L_b\}$ such that $|s_1 \dots s_n|_U = [s_1 \dots s_i|_D$ and

$$ h_i := |s_1 \dots s_i|_U - [s_1 \dots s_i|_D \ge 0 \quad (i = 1, \dots, n), \quad (2.22) $$

where $|s_1 \dots s_i|_U$ is the number of letters U in the word $s_1 \dots s_i$.

A Laguerre history (resp. restricted Laguerre history) of length $n$ is a pair $(\mathbf{s}, \mathbf{p})$, where $\mathbf{s}$ is a 2-Motzkin path $s_1 \dots s_n$ and $\mathbf{p} = (p_1, \dots, p_n)$ with $0 \le p_i \le h_{i-1}$ (resp. $0 \le p_i \le h_{i-1} - 1$ if $s_i = L_b$ or D) and $h_0 = 0$. Let $\mathcal{L}\mathcal{H}_n$ (resp. $\mathcal{L}\mathcal{H}_n^*$) be the set of Laguerre histories (resp. restricted Laguerre histories) of length $n$. There are several well-known bijections between $\mathcal{S}_n$ and $\mathcal{L}\mathcal{H}_n^*$ and $\mathcal{L}\mathcal{H}_{n-1}$, see [12, 4] and references therein.

## 2.6 Françon-Viennot bijection

We recall a version of Françon and Viennot's bijection $\psi_{FV} : \mathcal{S}_{n+1} \to \mathcal{L}\mathcal{H}_n$. Given $\sigma \in \mathcal{S}_{n+1}$, the Laguerre history $(\mathbf{s}, \mathbf{p})$ is defined as follows:

$$ s_i = U (\text{resp. D}, L_r, L_b) \text{ if } i \in \text{Val}\sigma (\text{resp. } i \in \text{Pk}\sigma, i \in \text{Da}\sigma, i \in \text{Dd}\sigma) \quad (2.23) $$

and $p_i = (2-13)_i \sigma$ for $i = 1, \dots, n$.

**Theorem 2.4.** The mapping $\psi := \psi_{FV} \circ \Psi^{-1}$ is a bijection from $\mathcal{S}_{n+1}$ to $\mathcal{L}\mathcal{H}_n$. If $\psi(\sigma) = (\mathbf{s}, \mathbf{p})$ with $\sigma \in \mathcal{S}_{n+1}$, then, for $i = 1, \dots, n$,

$$ s_i = U (\text{resp. D}, L_r, L_b) \text{ if } i \in \text{Cval}^* \sigma (\text{resp. } i \in \text{Cpk}^* \sigma, i \in \text{Cda}^* \sigma \cup \text{Fix}^* \sigma, i \in \text{Cdd}^* \sigma) \quad (2.24) $$

with $p_i = \text{nest}_i \sigma$.

*Proof.* This follows from **Theorem 2.2** by comparing (2.24) with (2.23), see the commutative diagram in **Figure 1**. $\square$

**Corollary 2.5.** The two sextuple statistics

$$ (\text{nest}, \text{cros}, \text{exc}, \text{cdd}^*, \text{cda}^* + \text{fix}^*, \text{cpk}^*) \quad \text{and} \quad (2-13, 31-2, \text{des}, \text{da}, \text{dd}, \text{pk} - 1) $$

are equidistributed on $\mathcal{S}_n$.

We recall two bijections $\phi_{FZ}$ and $\phi_{FV}$ from $\mathcal{S}_n$ to $\mathcal{L}\mathcal{H}_n^*$.
## 2.7 Restricted Françon–Viennot bijection

We recall a restricted version of Françon and Viennot's bijection $\phi_{FV}: \mathfrak{S}_n \to \mathcal{L}\mathcal{H}_n^*$. Given $\sigma \in \mathfrak{S}_n$, the Laguerre history $(\mathbf{s}, \mathbf{p})$ is defined as follows:

$$s_i = U(\text{resp. } D, L_r, L_b) \text{ if } i \in \text{Lval}\sigma (\text{resp. } i \in \text{Lpk}\sigma, i \in \text{Lda}\sigma, i \in \text{Ldd}\sigma) \quad (2.25)$$

and $p_i = (2-31)_i \sigma$ for $i = 1, \dots, n$.

## 2.8 Foata–Zeilberger bijection

This bijection $\phi_{FZ}$ encodes permutations using cyclic statistics. Given $\sigma \in \mathfrak{S}_n$, $\phi_{FZ}: \mathfrak{S}_n \to \mathcal{L}\mathcal{H}_n^*$ is for $i = 1, \dots, n$,

$$s_i = U(\text{resp. } D, L_r, L_b) \text{ if } i \in \text{Cval}\sigma (\text{resp. } i \in \text{Cpk}\sigma, i \in \text{Cda}\sigma \cup \text{Fix}\sigma, i \in \text{Cdd}\sigma) \quad (2.26)$$

with $p_i = \text{nest}_i \sigma$. By (2.7) and (2.8), we can build a comutative diagram, see the right diagram of Figure 1.

By contracting the continued fraction (1.1) we derive the two J-type continued fraction formulae (cf. [6])

$$\sum_{n \ge 0} A_{n+1}(t)z^n = \frac{1}{1 - (1+t) \cdot z - \frac{1 \cdot 2 \cdot t \cdot z^2}{1 - 2(1+t) \cdot z - \frac{2 \cdot 3 \cdot t \cdot z^2}{1 - \dots}}} \quad (2.27)$$

and

$$\sum_{n \ge 0} A_n(t)z^n = \frac{1}{1 - (1 + 0 \cdot t) \cdot z - \frac{1^2 \cdot z^2}{1 - (2 + 1 \cdot t) \cdot z - \frac{2^2 \cdot t \cdot z^2}{1 - \dots}}} \quad (2.28)$$

In view of Flajolet's combinatorial interpretation in terms of weighted Motzkin paths for generic J-type continued fraction expansions [6], Françon–Viennot's bijection $\psi_{FV}$ (resp. its restricted version $\phi_{FV}$) between permutations and *Laguerre histories* provides a bijective proof of (2.27) (resp. (2.28)), while Foata–Zeilberger's bijection $\psi_{FZ}$ [8] gives a bijective proof of (2.28). More precisely, Françon–Viennot [9] set up a bijection (and its restricted version) from permutations to *Laguerre histories* using *linear statistics of permutation*, while Foata–Zeilberger's bijection [8] uses *cyclic statistics of permutations*. Clarke-Steingrímsson-Zeng [4] gave a direct bijection $\Phi$ on permutations converting statistic des into exc on permutations, and linking the restricted Françon–Viennot's bijection $\phi_{FV}$ to
<figure><img src="image_2.png" /><figcaption>Figure 1: Bijections $\Phi = \phi_{FZ}^{-1} \circ \phi_{FV}$ and $\psi = \psi_{FV} \circ \Psi^{-1}$.</figcaption></figure>

Foata-Zeilberger bijection $\phi_{FZ}$, see Figure 1. As a variation of $\Phi$, Shin and Zeng [14] constructed a bijection $\Psi$ on permutations to derive a cycle version of linear statistics on permutations, which are obtained via Françon-Viennot bijection $\psi_{FV}$. One of our main results (cf. Theorem 2.4) shows that a direct description of the bijection $\psi := \psi_{FV} \circ \Psi^{-1}$ from $\mathfrak{S}_{n+1}$ to $\mathcal{L}\mathcal{H}_n$ is straightforward.

## 2.9 Pattern avoidances and 2-Motzkin paths

A permutation $\sigma$ is called 231-avoiding permutation if there is no triple of indices $i < j < k$ such that $\sigma(k) < \sigma(i) < \sigma(j)$. The Narayana polynomials are defined by

$$N_n(t) = \sum_{\sigma \in \mathfrak{S}_n(231)} t^{\text{des} \sigma},$$

where $\mathfrak{S}_n(231)$ is the set of 231-avoiding permutations in $\mathfrak{S}_n$. It is well known that Narayana polynomial is $\gamma$-positive and have the expansion [13, Chapter 4]:

$$N_n(t) = \sum_{k=0}^{n/2} \tilde{\gamma}_{n,j} t^j (1+t)^{n-1-2j}, \qquad (2.29)$$

where $\tilde{\gamma}_{n,j} = |\{\sigma \in \mathfrak{S}_n(231) : \text{des}(\sigma) = \text{pk}(\sigma) = j\}|$. As for Eulerian polynomials, by contraction, from

$$\sum_{n \ge 0} N_n(t) z^n = 1/1 - z/1 - t \cdot z/1 - z/1 - t \cdot z/1 - \dots \qquad (2.30)$$

we derive immediately the following continued fractions

$$\sum_{n \ge 0} N_{n+1}(t) z^n = \frac{1}{1 - (1+t) \cdot z - \frac{t \cdot z^2}{1 - (1+t) \cdot z - \frac{t \cdot z^2}{1 - \dots}}} \qquad (2.31)$$
and

$$ \sum_{n \ge 0} N_n(t) z^n = \frac{1}{1 - z - \frac{t \cdot z^2}{1 - (1+t) \cdot z - \frac{t \cdot z^2}{1 - (1+t) \cdot z - \dots}}} \quad (2.32) $$

Note that $N_n(1)$ is the n-th Catalan number $C_n = \frac{1}{n+1} \binom{2n}{n}$, there are several well-known q-Narayana polynomials in the literature, see [3] and [10].

Given two permutations $\sigma \in \mathfrak{S}_n$ and $\tau \in \mathfrak{S}_k$, we say that $\sigma$ contains the pattern $\tau$ if there exists a set of indices $1 \le i_1 < i_2 < \dots < i_k \le n$ such that the subsequence $\sigma(i_1)\sigma(i_2)\dots\sigma(i_k)$ of $\sigma$ is order-isomorphic to $\tau$. Otherwise, $\sigma$ is said to avoid $\tau$. For example, the permutation 15324 contains the pattern 321 and avoids the pattern 231. The set of permutations of length $n$ that avoid patterns $\tau_1, \tau_2, \dots, \tau_m$ is denoted as $\mathfrak{S}_n(\tau_1, \tau_2, \dots, \tau_m)$.

Moreover we shall consider the so-called vincular patterns. The number of occurrences of vincular patterns 31-2, 2-31, 2-13 and 13-2 in $\pi \in \mathfrak{S}_n$ are defined (cf. (2.1)) by

$$ \begin{aligned} (31-2) \pi &= \#\{(i,j) : i+1 < j \le n \text{ and } \pi(i+1) < \pi(j) < \pi(i)\}, \\ (2-31) \pi &= \#\{(i,j) : j < i < n \text{ and } \pi(i+1) < \pi(j) < \pi(i)\}, \\ (2-13) \pi &= \#\{(i,j) : j < i < n \text{ and } \pi(i) < \pi(j) < \pi(i+1)\}, \\ (13-2) \pi &= \#\{(i,j) : i+1 < j \le n \text{ and } \pi(i) < \pi(j) < \pi(i+1)\}. \end{aligned} \quad (2.33) $$

Similarly, we use $\mathfrak{S}_n(31-2)$ to denote the set of permutations of length $n$ that avoid the vincular pattern 31-2, etc. In order to apply Laguerre history to count pattern-avoiding permutations, we will need the following results in [10, Lemmas 2.8 and 2.9].

**Lemma 2.6** ([10, Lemma 2.8]). For any $n \ge 1$, we have

$$ \mathfrak{S}_n(2-13) = \mathfrak{S}_n(213), \quad \mathfrak{S}_n(31-2) = \mathfrak{S}_n(312), \quad (2.34) $$

$$ \mathfrak{S}_n(13-2) = \mathfrak{S}_n(132), \quad \mathfrak{S}_n(2-31) = \mathfrak{S}_n(231). \quad (2.35) $$

**Lemma 2.7** ([10, Lemma 2.9]). (i) A permutation $\pi \in \mathfrak{S}_n$ belongs to $\mathfrak{S}_n(321)$ if and only if $\text{nest}\pi = 0$

(ii) The mapping $\Phi$ has the property that $\Phi(\mathfrak{S}_n(231)) = \mathfrak{S}_n(321)$.

We use $\mathcal{CM}_n$ to denote the set of 2-Motzkin paths of length $n$ and $\mathcal{CM}_n^*$ to denote its subset that is composed of 2-Motzkin paths without $L_b$-step at level zero, i.e., if $h_{i-1} = 0$, then $s_i \ne L_b$. Noticing that the generating function $\sum_{n \ge 0} |\mathcal{CM}_n^*|z^n$ has the continued fraction expansion (2.32) with $t = 1$, we derive that $|\mathcal{CM}_n^*| = C_n$. Similarly, by (2.31) we see that $|\mathcal{CM}_n| = C_{n+1}$.

Let $\tilde{\phi}_{FV}$ (resp. $\tilde{\phi}_{FZ}$, $\tilde{\psi}_{FV}$, $\tilde{\psi}$, $\tilde{\Psi}$, $\tilde{\Phi}$) be the restriction of $\phi_{FV}$ (resp. $\phi_{FZ}$, $\psi_{FV}$, $\psi$, $\Psi$, $\Phi$) on the sets $\mathfrak{S}_n(231)$ (resp. $\mathfrak{S}_n(321)$, $\mathfrak{S}_{n+1}(213)$, $\mathfrak{S}_{n+1}(321)$, $\mathfrak{S}_{n+1}(213)$, $\mathfrak{S}_n(231)$). By Lemmas 2.6 and 2.7 and Figure 1, we obtain the diagrams in Figure 2.
<figure><img src="image_3.png" /><figcaption>Figure 2: Bijections $\tilde{\Psi} = \tilde{\psi}^{-1} \circ \tilde{\psi}_{FV}$ and $\tilde{\Phi} = \tilde{\phi}_{FZ}^{-1} \circ \tilde{\phi}_{FV}$.</figcaption></figure>

# 3 Main results

For a finite set of permutations $\Omega$ and $m$ statistics $\text{stat}_1, \dots, \text{stat}_m$ on $\Omega$, we define the generating polynomial

$$P^{(\text{stat}_1, \dots, \text{stat}_m)}(\Omega; t_1, \dots, t_m) := \sum_{\sigma \in \Omega} t_1^{\text{stat}_1 \sigma} \dots t_m^{\text{stat}_m \sigma}. \qquad (3.1)$$

**Theorem 3.1.** For $n \ge 1$,

$$P^{(\text{nest},\text{cros},\text{exc},\text{fix})}(\mathfrak{S}_n; p, q, tq, r) = \left(\frac{1+xt}{1+x}\right)^n P^{(\text{nest},\text{cros},\text{cpk},\text{exc},\text{fix})}\left(\mathfrak{S}_n; p, q, \frac{(1+x)^2t}{(x+t)(1+xt)}, \frac{q(x+t)}{1+xt}, \frac{(1+x)r}{1+xt}\right), \quad (3.2)$$

equivalently,

$$P^{(\text{nest},\text{cros},\text{cpk},\text{exc},\text{fix})}(\mathfrak{S}_n; p, q, x, qt, r) = \left(\frac{1+u}{1+uv}\right)^n P^{(\text{nest},\text{cros},\text{exc},\text{fix})}\left(\mathfrak{S}_n; p, q, qv, \frac{(1+uv)r}{1+u}\right), \quad (3.3)$$

where $u = \frac{1+t^2-2xt-(1-t)\sqrt{(1+t)^2-4xt}}{2(1-x)t}$ and $v = \frac{(1+t)^2-2xt-(1+t)\sqrt{(1+t)^2-4xt}}{2xt}$.

**Remark 3.2.** Cooper et al. [5, Theorem 11] have recently proved the $p = q = 1$ case of (3.2) by applying Sun and Wang's CMFS action [17].

We define the polynomial

$$A_n(p, q, t) := \sum_{\sigma \in \mathfrak{S}_n} p^{\text{nest}\sigma} q^{\text{cros}\sigma} t^{\text{exc}\sigma}. \qquad (3.4)$$

The following is a generalization of Stembridge's identity (1.4).
**Theorem 3.3.** For $n \ge 1$, we have

$$A_n(p, q, t) = \left(\frac{1+xt}{1+x}\right)^{n-1} p^{(\text{nest},\text{cros},\text{cpk}^*,\text{exc})} \left(\mathfrak{S}_n; p, q, \frac{(1+x)^2t}{(x+t)(1+xt)}, \frac{x+t}{1+xt}\right), \quad (3.5)$$

equivalently,

$$p^{(\text{nest},\text{cros},\text{cpk}^*,\text{exc})}(\mathfrak{S}_n; p, q, x, t) = \left(\frac{1+u}{1+uv}\right)^{n-1} A_n(p, q, v), \quad (3.6)$$

where $u = \frac{1+t^2-2xt-(1-t)\sqrt{(1+t)^2-4xt}}{2(1-x)t}$ and $v = \frac{(1+t)^2-2xt-(1+t)\sqrt{(1+t)^2-4xt}}{2xt}$.

**Remark 3.4.** By Corollary 2.5 and (3.5), when $x = 1$ or $p = q = 1$ we recover two special cases of (3.5) due to Brändén's result [2, (5.1)] and Zhuang [18, Theorem 4.2], respectively.

## Acknowledgements

Part of this work was done during the first and second authors' studies at Institut Camille Jordan, Université Claude Bernard Lyon 1.

## References

[1] C. A. Athanasiadis. "Gamma-positivity in combinatorics and geometry". Sém. Lothar. Combin. 77 (2016-2018), Art. B77i, 64.

[2] P. Brändén. "Actions on permutations and unimodality of descent polynomials". European J. Combin. 29.2 (2008), pp. 514–531. Link.

[3] S.-E. Cheng, S. Elizalde, A. Kasraoui, and B. Sagan. "Inversion polynomials for 321-avoiding permutations". Discrete Math. 313.22 (2013), pp. 2552–2565. Link.

[4] R. J. Clarke, E. Steingrímsson, and J. Zeng. "New Euler-Mahonian statistics on permutations and words". Adv. in Appl. Math. 18.3 (1997), pp. 237–270. Link.

[5] M. C. Cooper, W. S. Jones, and Y. Zhuang. "On the joint distribution of cyclic valleys and excedances over conjugacy classes of $\mathfrak{S}_n$". Adv. in Appl. Math. 115 (2020), pp. 101–999, 15. Link.

[6] P. Flajolet. "Combinatorial aspects of continued fractions". Discrete Mathematics 32.2 (1980), pp. 125–161. Link.

[7] D. Foata and M.-P. Schützenberger. Théorie géométrique des polynômes eulériens. Lecture Notes in Math., Vol. 138. Springer-Verlag, Berlin-New York, 1970, pp. v+94.
[8] D. Foata and D. Zeilberger. "Denert's permutation statistic is indeed Euler-Mahonian". *Stud. Appl. Math.* **83.1** (1990), pp. 31–59. Link.

[9] J. Françon and G. Viennot. "Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d'Euler et nombres de Genocchi". *Discrete Mathematics* **28.1** (1979), pp. 21–35. Link.

[10] S. Fu, D. Tang, B. Han, and J. Zeng. "(*q*, *t*)-Catalan numbers: gamma expansions, pattern avoidances, and the (−1)-phenomenon". *Adv. in Appl. Math.* **106** (2019), pp. 57–95. Link.

[11] B. Han, J. Mao, and J. Zeng. "Eulerian polynomials and excedance statistics". Preprint. 2019. arXiv:1908.01084.

[12] A. de Médicis and X. G. Viennot. "Moments des *q*-polynômes de Laguerre et la bijection de Foata-Zeilberger". *Adv. in Appl. Math.* **15.3** (1994), pp. 262–304. Link.

[13] T. K. Petersen. *Eulerian numbers*. Birkhäuser/Springer, New York, 2015, pp. xviii+456. Link.

[14] H. Shin and J. Zeng. "The symmetric and unimodal expansion of Eulerian polynomials via continued fractions". *European J. Combin.* **33.2** (2012), pp. 111–127. Link.

[15] H. Shin and J. Zeng. "Symmetric unimodal expansions of excedances in colored permutations". *European J. Combin.* **52**.part A (2016), pp. 174–196. Link.

[16] T. J. Stieltjes. "Sur la réduction en fraction continue d'une série procédant suivant les puisances descendantes d'une variable". *Ann. Fac. Sci. Toulouse Sci. Math. Sci. Phys.* **3** (1889), H1–H17.

[17] H. Sun and Y. Wang. "A group action on derangements". *Electron. J. Combin.* **21.1** (2014), Paper 1.67, 5.

[18] Y. Zhuang. "Eulerian polynomials and descent statistics". *Adv. in Appl. Math.* **90** (2017), pp. 86–144. Link.