Some multivariate polynomials for doubled permutations

1.   Introduction

For a fixed modulus $x\in (0,1)$, the Jacobi elliptic function ${{\rm{sn\,}}}(z, x)$ is the inverse of an elliptic integral, i.e.,

The other two Jacobi elliptic functions are respectively defined by

These functions appear in a variety of problems in physics and have been extensively studied in mathematical physics, algebraic geometry, combinatorics and number theory (see [5,6,8,9,11,12,19,20,21,27,28] for instance). When $x = 0$ or $x = 1$, the Jacobi elliptic functions degenerate into trigonometric or hyperbolic functions:

The three Jacobi elliptic functions are connected by the differential system (see [2]):

Note that

where ${\mathrm i} = \sqrt{-1}$ and $E_n$ is the number of alternating permutations (also known as up-down permutations) in ${\mathfrak{S}}_n$ (see [26]). The Taylor series expansions of these Jacobian elliptic functions are given as follows:

Defining the Laplace-Borel transforms of ${{\rm{sn\,}}}$ and ${{\rm{cn\,}}}$ by:

i.e., the series obtained from (3) and (4) by replacing $z^n/n!$ by $z^n$, Rogers and Stieltjes [21,27] found the following continued fractions expansions.

According to [12], the question of the possible combinatorial significance of the coefficients of $J_n(x)$ in

was first raised by Schützenberger. The first combinatorial interpretation was given by Viennot [28], and is expressed in terms of so-called Jacobi permutations. Using his combinatorial theory of continued fractions Flajolet [11] proved that the coefficients of ${{\rm{cn\,}}}(z, x)$ count classes of alternating (up-and-down) permutations based on the parity of peaks. Dumont [8] finally discovered some further relations between these functions and the cycle structure of permutations. Flajolet-Françon [12] gave an interpretation of the elliptic functions as generating functions of doubled permutations.

A polynomial $f(x) = \sum_i a_i x^i\in{\mathbb{R}}[x]$ is called $\gamma$-positive if $f(x) = \sum_{i = 0}^{\lfloor n/2 \rfloor}\gamma_ix^i(1+x)^{n-2i}$ for $n\in{\mathbb{N}}$ and nonnegative reals $\gamma_0,\gamma_1,\ldots,\gamma_{\lfloor n/2\rfloor}$, the notion of $\gamma$-positivity appeared first in the work of Foata and Schützenberger [13]. A recent survey on $\gamma$-positivity in combinatorics and geometry was given by Athanasiadis [1]. In a series of papers Shin and Zeng [22,23,24] exploited the combinatorial theory of continued fractions to derive various $\gamma$-positivity results.

In this paper, by generalizing the continued fraction expansions of Rogers and Stieltjes, we generalize Flajolet and Françon's the combinatorial interpretation of the Taylor coefficients of the Jacobian elliptic functions. Furthermore, we show that the Taylor coefficients of the generalized Jacobian elliptic functions are $\gamma$-positive. The main tools are the combinatorial theory of continued fractions due to Flajolet and bijections due to Françon-Viennot, Foata-Zeilberger and Clarke-Steingrímsson-Zeng.

2.   Main results

We follow [4,17,16,22,23] for notations and the nomenclature of various permutation statistics. First we recall three classical involutions defined on ${\mathfrak{S}}_n$, namely, the reverse, complement and the composition of the two. For $\pi\in{\mathfrak{S}}_n$,

Denote by $\pi^{-1}$ the inverse permutation of $\pi$. If we use the standard two-line notation to write $\pi$, then $\pi^{-1}$ is obtained by switching the two lines and rearranging the columns to make the first line increasing. For instance, if $\pi = \left(\begin{array}{ccc} 1 & 2 & 3\\ 2 & 3 & 1 \end{array}\right)$, then $\pi^{-1} = \left(\begin{array}{ccc} 1 & 2 & 3\\ 3 & 1 & 2 \end{array}\right)$.

Let $\mathfrak{S}_{n}$ be the set of permutations of $[n] = \{1,2,\dots,n\}$. Given a permutation $\pi = \pi(1)\pi(2)\cdots\pi(n)\in \mathfrak{S}_{n}$ we say that $i\in[n-1]$ is a descent (resp. excedance) of $\pi$ if $\pi(i)>\pi(i+1)$ (resp. $\pi(i)>i$). Let ${\mathsf{des}}\,\pi$ (resp. ${\mathsf{exc}}\,\pi$) denote the number of descents (resp. excedances) of $\pi$.

Definition 2.1. For $\pi\in{\mathfrak{S}}_n$, let $\pi(0) = \pi(n+1) = 0$. Then any entry $\pi(i)$ ($i\in[n]$) can be classified according to their ordinal type into four categories:

● a peak if $\pi(i-1)<\pi(i)$ and $\pi(i)>\pi(i+1)$;

● a valley if $\pi(i-1)>\pi(i)$ and $\pi(i)<\pi(i+1)$;

● a double ascent if $\pi(i-1)<\pi(i)$ and $\pi(i)<\pi(i+1)$;

● a double descent if $\pi(i-1)>\pi(i)$ and $\pi(i)>\pi(i+1)$.

Let ${\mathsf{pk}}\:\pi$ (resp. ${\mathsf{val}}\:\pi$, ${\mathsf{da}}\:\pi$, ${\mathsf{dd}}\:\pi$) be the number of peaks (resp. valleys, double ascents, double descents) in $\pi$. Note that for $\pi\in{\mathfrak{S}}_n$, ${\mathsf{pk}}\,\pi+{\mathsf{dd}}\, \pi = {\mathsf{des}}\,\pi+1$.

For $\sigma\in {\mathfrak{S}}_n$ with convention 0–$\infty$, i.e., $\sigma(0) = 0$ and $\sigma(n+1) = \infty$, any entry $\pi(i)$ ($i\in[n]$) can be classified according to their left ordinal type into four categories: let ${\mathsf{Lpk}}$ (resp. ${\mathsf{Lval}}$, ${\mathsf{Lda}}$, ${\mathsf{Ldd}}$) be the set of $peaks$ (resp. $valleys$, $double \;ascents$ and $double \;decents$) and denote the corresponding cardinality by ${\mathsf{lpk}}$ (resp. ${\mathsf{lval}}$, ${\mathsf{lda}}$ and ${\mathsf{ldd}}$).

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

Any entry $\pi(i)$ ($i\in[n]$) can be classified according to their star cyclic type into four categories:

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

Definition 2.3. A permutation is a doubled permutation iff for all $0\leq i\leq \lfloor (n-2)/2\rfloor$, elements (i.e. values) $2i+1$ and $2i+2$ are of the same ordinal type. The set of doubled permutations is denoted by ${\mathcal{DP}}_{n}$. A permutation is a star doubled permutation iff for all $0\leq i\leq \lfloor (n-2)/2\rfloor$, elements (i.e. values) $2i+1$ and $2i+2$ are of the same star cyclic type. The set of star doubled permutations is denoted by ${\mathcal{DP}}^*_{n}$.

For example, $\pi_1 = 6315427\in{\mathcal{DP}}_7$ since $1$ and $2$ (resp. $3$ and $4$, $5$ and $6$) are valleys (resp. double descents, peaks) of $\pi_1$. $\pi_2 = 6732451\in{\mathcal{DP}}^*_7$ since $\{1, 2\}\in {\rm{Cval }}^*\pi_2$, $\{3, 4\}\in {\rm{Cdd }}^*\pi_2$ and $\{5, 6\}\in {\rm{ Cpeak}}^*\pi_2$.

The first goal of this paper is to explore the coefficients in the Taylor series expansion of Jacobi elliptic functions ${{\rm{sn\,}}}(z, x)$ by generalizing the continued fractions of (6).

For $\sigma \in {\mathfrak{S}}_n$, the statistic $({31\text{-}2})\, \sigma$ (resp. $({13\text{-}2})\, \sigma$) is the number of pairs $(i,j)$ such that $2\leq i<j\leq n$ and $\sigma(i-1)>\sigma(j)>\sigma(i)$ (resp. $\sigma(i-1)<\sigma(j)<\sigma(i)$). Similarly, the statistic $({2\text{-}13})\, \sigma$ (resp. $({2\text{-}31})\, \sigma$) is the number of pairs $(i,j)$ such that $1\leq i<j\leq n-1$ and $\sigma(j+1)>\sigma(i)>\sigma(j)$ (resp. $\sigma(j+1)<\sigma(i)<\sigma(j)$). Moreover, define

Let ${\mathsf{cros}} = \sum_{i = 1}^n{\mathsf{cros}}_i$ and ${\mathsf{nest}} = \sum_{i = 1}^n{\mathsf{nest}}_i$.

Let $J_{2n+1}(p, q, x, u, v, w)$ be the polynomials defined by the continued fraction expansion

where $[n]_{p,q} = (p^n-q^n)/(p-q)$.

Theorem 2.4. We have

As $J_{2n+1}(x): = J_{2n+1}(1, 1, x, 1, 1, 1)$, we derive

Eq. (18) is due to Flajolet-Françon[12].

Theorem 2.5. We have

where

and

Moreover, for all $0\le k \leq \lfloor n/2\rfloor$, the following divisibility holds

In particular, we obtain the following expansion of $J_{2n+1}(x)$ from (20).

Corollary 1. For all $n\geq1$, we have

Remark 1. Using context-free grammar Ma-Ma-Yeh-Zhou gave another interpretation of $\gamma$-coefficients in increasing trees, see [20,Eq. (14)] and [20,Corollary 20], it would be interesting to find a direct bijection between ${\mathcal{DP}}_{2n+1, 2k}$ and the $\gamma$-coefficients in [20].

The second goal of this paper is to explore the coefficients in the Taylor series expansion of Jacobi elliptic functions ${{\rm{cn\,}}}(z, x)$ by generalizing the continued fractions of (7).

Definition 2.6. For $\sigma\in {\mathfrak{S}}_n$, any entry $\sigma(i)$ ($i\in[n]$) can be classified according to their cyclic ordinal type into four cases:

● 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(resp. fixed point) if $i = \sigma^{-1}(x)<x$ and $x<\sigma(x)$(resp. $x = \sigma(x)$);

● a double drop if $i = \sigma^{-1}(x)>x$ and $x>\sigma(x)$.

Let ${\mathsf{cpk}} \,\sigma$ (resp. ${\mathsf{cval}} \,\sigma$, ${\mathsf{cda}} \,\sigma$, ${\mathsf{cdd}} \,\sigma$, ${\mathsf{fix}} \,\sigma$) be the number of cyclic peaks (resp. valleys, double excedances, double drops, fixed points) in $\sigma$.

Definition 2.7. For $\sigma\in {\mathfrak{S}}_n$ with convention 0–$\infty$, a double ascent $\sigma(i)$ of $\sigma$ ($i \in [n]$) is said to be a foremaximum if $\sigma(i)$ is a left-to-right maximum of $\sigma$, i.e., $\sigma(j)<\sigma(i)$ for all $1\leq j<i$. Denote the number of foremaxima of $\sigma$ by ${\mathsf{fmax}}\,\sigma$.

For instance, ${\mathsf{lda}}(42157368) = 3$, but ${\mathsf{da}}(42157368) = 2$ and ${\mathsf{fmax}}(42157368) = 2$.

Definition 2.8. A permutation $\pi$ is said to be a left doubled permutation iff for all $0\leq i\leq \lfloor (n-2)/2\rfloor$, elements (i.e. values) $2i+1$ and $2i+2$ in $\pi$ are of the same left ordinal type. The set of left doubled permutation is denoted by ${\mathcal{LDP}}_n$. A permutation $\pi$ is said to be a cyclic doubled Permutation iff for all $0\leq i\leq \lfloor (n-2)/2\rfloor$, elements (i.e. values) $2i+1$ and $2i+2$ in $\pi$ are of the same cyclic ordinal type. The set of cyclic doubled permutation is denoted by ${\mathcal{CDP}}_n$.

Let $J_{2n}(p, q, x, u, v,, w, y)$ be the polynomials defined by the continued fraction expansion

Theorem 2.9. We have

Since $J_{2n}(x) = J_{2n}(1, 1, x, 1, 1, 1)$, we derive

Eq. (27) is due to Flajolet-Françon [12].

When $u = 0$ and $t = v = 1$ we can write

where $b_{2n,2k,2j}(p,q)$ is a polynomial in $p$ and $q$ with non negative integral coefficients. Let ${\mathcal{CDP}}_{2n,2k,2j}$ denote the subset of all the permutations $\sigma\in {\mathcal{CDP}}_{2n}$ with exactly $2k$ cyclic valleys, $2j$ fixed points, and without double drops, and let ${\mathcal{LDP}}_{2n,2k,2j}$ denote the subset of all permutations $\sigma\in {\mathcal{LDP}}_{2n}$ with exactly $2k$ valleys and $2j$ double ascents, which are all foremaxima. We derive the following combinatorial interpretation of $b_{2n,2k,2j}(p,q)$ from Theorem 2.9.

Corollary 2. We have

In particular, when $j = 0$, we obtain

where ${\mathcal{DD}}_{2n}: = \{\pi\in {\mathcal{CDP}}_{2n}, {\mathsf{fix}}\,\pi = 0\}$.

Recall (see [22]) that a coderangement is a permutation without foremaximum. Let ${\mathcal{DD}}^*_{2n}$ be the subset of ${\mathcal{LDP}}_{2n}$ consisting of coderangements, that is, ${\mathcal{DD}}^*_n = \{\sigma\in{\mathcal{LDP}}_{2n}: {\mathsf{fmax}}\,\sigma = 0\}.$ Thus, ${\mathcal{DD}}_{2n,2k,0}$ is the subset of derangements $\sigma\in {\mathcal{DD}}_{2n}$ with exactly $2k$ cyclic valleys, and without double drops, and ${\mathcal{DD}}^*_{2n,2k,0}$ is the subset of coderangements $\sigma\in {\mathcal{DD}}^*_{n}$ with exactly $2k$ valleys and without double ascents. The following is our main result about the polynomial

Theorem 2.10. We have

A pair of integers $(i,j)$ is an inversion of $\sigma\in {\mathfrak{S}}_n$ if $i<j$ and $\sigma(i)>\sigma(j)$. Let ${\mathsf{inv}}\:\sigma$ be the inverion number of $\sigma$.

As ${\mathsf{inv}} = {\mathsf{exc}}+2{\mathsf{nest}}+{\mathsf{cros}}$ (cf. [16,Eq. (2.41)]), taking $(p, q, x, u, v, w) = (q, 1, x, 1, 1, 1)$ (resp. $(p, q,x, u, v, w) = (q^2, q, xq, 1, 1, 1)$) in Eq. (32), we obtain the following corollary.

Corollary 3. For all positive integers $n$ and for each statistic ${\mathsf{stat}}\,\in\{{\mathsf{nest}}, {\mathsf{inv}}\}$,

For any permutation $\sigma\in {\mathfrak{S}}_n$, we denote by ${\mathsf{cyc}}\,\sigma$ the number of its cycles. We give the following expansion.

Theorem 2.11. We have

The rest of this paper is organized as follows. In Section 3, we recall some definitions and preliminaries of combinatorial theory of continued fractions. In Sections 4–7 we shall prove Theorem 2.4, Theorem 2.5, Theorem 2.9, Theorem 2.10 and Theorem 2.11, respectively. In Section 8, we refine the enumeration results on alternating permutations, which are related to the combinatorial interpretations of Jacobi elliptic functions.

3.   Definitions and preliminaries

A Motzkin path of length $n$ in the plan ${\mathbb{N}}\times {\mathbb{N}}$ is a sequence of points $(s_{0}, \ldots, s_{n})$, where $s_{0} = (0,0)$, $s_{i}-s_{i-1} = (1,0), (1,\pm 1)$ and $s_{n} = (n,0)$. Each step $(s_{i-1}, s_{i})$ is called East (resp. North-East, South-East) if $s_{i}-s_{i-1} = (1,0)$ (resp. $s_{i}-s_{i-1} = (1,1)$, $s_{i}-s_{i-1} = (1,-1)$). The height of the step $(s_{i-1}, s_{i})$ denoted by $h_i$ is the ordinate of $s_{i-1}$.

A 2-Motzkin path is a Motzkin path consists of two types of horizontal steps, either blue or red. The set of 2-Motzkin path of length $n\geq 1$ is denoted by $\mathcal{CM}_n$. Denoting the North-East step (resp. East blue step, East red step, South-East step) by a (resp. $b$, $b'$, $c$), see Figure 1 for a 2-Motzkin path. If we weight each East blue (resp. East red, North-East, South-East) step of height $i$ by $b_{i}$ (resp. $b'_{i}$, $a_{i}$ and $c_{i}$), and define the weight of $\gamma$ by the product of its step weights denoted by $w(\gamma)$. Then,

A 2-Motzkin path is a doubled path if the step at odd position is always followed by a step of the same type. See Figure 1 for a doubled path $\gamma$, whose wieght is $w(\gamma) = a_0a_1b_2b_2c_2c_1a_0a_1c_2c_1b'_0b'_0$.

Grouping steps 2 by 2 in a doubled path of length $2n$ yields a 2-Motzkin path of length $n$, by (35) we obtain the following lemma.

Lemma 3.1. If $\rm{DM}_{2n}$ is the set of doubled paths of length $2n$, then

Definition 3.2. A Laguerre history (restricted Laguerre history) of length $n$ is a couple $(\gamma, (p_{1}, \ldots, p_{n}))$, where $\gamma$ is a Motzkin path of length $n$ and $(p_{1}, \ldots, p_{n})$ is a sequence satisfying $0\leq p_{i}\leq h_i$ (resp. $0\leq p_{i}\leq h_i-1$ if $(s_{i-1}, s_i)$ is East red and South east). Denote by ${\mathcal{LH}}_n$ (resp. ${\mathcal{LH}}^*_{n}$) the set of Laguerre histories (resp. restricted Laguerre histories) of length $n$. Similarly, a doubled Laguerre history (restricted doubled Laguerre history) of length $n$ is a couple $(\gamma, (p_{1}, \ldots, p_{n}))$, where $\gamma$ is a doubled path of length $n$ and $(p_{1}, \ldots, p_{n})$ is a sequence satisfying $0\leq p_{i}\leq h_i$ (resp. $0\leq p_{i}\leq h_i-1$ if $(s_{i-1}, s_i)$ is East red and South east). Denote by ${\mathfrak{DH}}_n$ (resp. ${\mathfrak{DH}}^*_{n}$) the set of doubled Laguerre histories (resp. doubled restricted Laguerre histories) of length $n$.

4.   Proof of Theorem 2.4

Clarke-Steingrímsson-Zeng [4] gave a direct bijection $\Phi$ on permutations converting statistic ${\mathsf{des}}$ into ${\mathsf{exc}}$ on permutations, and linking the restricted Françon-Viennot's bijection to Foata-Zeilberger bijection. As a variation of $\Phi$, Shin and Zeng [23] constructed a bijection $\Psi$ on permutations to derive a cycle version of linear statistics on permutations. Recently, Yan-Zhou-Lin [29] constructed a bijection $\psi_{YZL}$ from ${\mathfrak{S}}_{n+1}$ to ${\mathcal{LH}}_n$. Han-Mao-Zeng [16] showed that Yan-Zhou-Lin's bijection $\psi_{YZL}$ is a composition of Françon-Viennot's bijection and Shin-Zeng's bijection $\Psi$, see [16,Theorem 2.5]. Further, Han-Mao-Zeng also give another bijection $\Psi^*$ on permutations converting statistic ${\mathsf{des}}$ into ${\mathsf{exc}}$ on permutations, see [16,Corollary 2.2].

Lemma 4.1 (Han-Mao-Zeng). For $\sigma\in{\mathfrak{S}}_n$, we have

and

Let

As ${\mathsf{exc}} = {\mathsf{wex}}^* = {\mathsf{cval}}^*+{\mathsf{cda}}^*+{\mathsf{fix}}^*$, ${\mathsf{des}} = {\mathsf{val}}+{\mathsf{dd}}$, by Lemma 4.1 and Definition 2.3, we obtain the following result.

Theorem 4.2. Let $\widetilde{\Psi^*}$ be the restriction of $\Psi^*$ on ${\mathcal{DP}}_{2n+1}$. Then $\widetilde{\Psi^*}$ is a bijection from ${\mathcal{DP}}_{2n+1}$ to ${\mathcal{DP}}^*_{2n+1}$. Moreover, for $\sigma\in{\mathcal{DP}}_{2n+1}$, we have

Proof of Theorem 2.4. For $i\in[2n+1]$, define $({31\text{-}2})_{k}\sigma$, $({2\text{-}31})_{k}\sigma$ and $({2\text{-}13})_{k}\sigma$ for $\sigma\in {\mathcal{DP}}_{2n+1}$ by

We use Françon-Viennot's bijection $\Psi_{FV} : {\mathcal{DP}}_{2n+1} \to {\mathfrak{DH}}_{2n}$. For any $\sigma\in {\mathcal{DP}}_{2n+1}$, the doubled Laguerre history $(s_{0}, \ldots, s_{2n}, p_{1},\ldots, p_{2n})$ is constructed as follows. Let $s_{0} = (0,0)$ and for $i = 1, \ldots, 2n$,

● the step $(s_{i-1}, s_{i})$ is North-East if $i$ is a valley,

● the step $(s_{i-1}, s_{i})$ is South-East if $i$ is a peak,

● the step $(s_{i-1}, s_{i})$ is East blue if $i$ is a double ascent,

● the step $(s_{i-1}, s_{i})$ is East red if $i$ is a double descent.

While $p_{i} = ({2\text{-}13})_{i}\sigma$ for $i = 1,\ldots, 2n$.

According to definition of $h_i$, $({31\text{-}2})_1\sigma + ({2\text{-}13})_1\sigma = 0 = h_1$. For $i>1$, if $i$ is a valley, we have

By inductions we have

Similarly, it is not difficult to prove by induction that $({31\text{-}2})_{i}\sigma+({2\text{-}13})_{i}\sigma = h_{i}$ if $i$ is a peak, double ascent or double descent.

Since $\sigma(0) = \sigma(2n+2) = 0$, so $2n+1$ must be a peak and ${\mathsf{val}}\,\sigma = {\mathsf{pk}}\, \sigma-1$. Thus $(s_{0}, \ldots, s_{2n}, p_{1},\ldots, p_{2n})$ is a doubled Laguerre history of length $2n$ and

where ${\rm{NE }} \gamma$, ${\rm{EB }} \gamma$, and ${\rm{ ER}}\gamma$ are the number of North-East steps, East blue steps, and East red steps of $\gamma$. Therefore,

where $[n]_{p,q} = (p^n-q^n)/(p-q)$. Given a doubled path $\gamma$, the weight of each step at height $k$ is created by using the following rules:

if the step is North-East, East blue, East red and South-East, respectively, and the weight of $\gamma$ is defined to be the product of the step weights. Summing over all the doubled paths of length $2n$ with the rules (41), we have

By Lemma 3.1, $J_{2n+1}(p,q,x,u,v,w)$ are the coefficients in the following continued fraction expansion,

by transforming $z$ to $-z^2$ and multiplying both sides by $z$, we obtain (16) immediately. This completes the proof of (16). This lead to (17) combining (39) and (16).

5.   Proof of Theorem 2.5

Proof of Theorem 2.5. In view of (43), for $0\leq k\leq {\lfloor{n/2\rfloor}}$, let $a_{2n+1,2k}(p,q,x,u,v)$ be the coefficient of $w^{2k}$ in $A_{2n+1}(p,q,x,u,v,w)$, i.e.,

Transforming $z$ and $w$ to $\frac{z}{(u^2+x^2v^2)}$ and $\frac{w(u^2+x^2v^2)}{x}$ in (43), respectively, we obtain

Since the right-hand side of the above identity is free of variables $x$, $u$, and $v$, the coefficient of $w^{2k} z^{n}$ in the left-hand side is a polynomial in $p$ and $q$ with nonnegative integral coefficients. Denote the coefficient of (45) by

On the other hand, Take $(p, q, x, u, v, w) = (p, q, 1, 1, 0, w)$ in (44), then the continued fraction (43) becomes the right-hand side of (45) immediately. With the definition of $a_{2n+1, 2k}$ in (21), we see that

With Eq. (44), this proves (20). Finally, since $(p+q)^2 \; |\; [2n-1]_{p,q} [2n]_{p,q}^2[2n+1]_{p, q}$ for all $n\ge 1$, each $w^2$ appears with a factor $(p+q)^2$ in the right-hand side of (45), and the polynomial $P_{2n+1,2k}(p,q)$ is divisible by $(p+q)^{2k}$. This completes the proof. In the rest of this section, we will provide a combinatorial proof of Corollary 1 via the modified Foata-Strehl actions on permutations.

Definition 5.1 (MFS-action). Let $\pi\in{\mathfrak{S}}_n$ with boundary condition $\pi(0) = \pi(n+1) = 0$, for any $a\in[n]$, the $a$-factorization of $\pi$ reads $\pi = w_1 w_2a w_3 w_4,$ where $w_2$ (resp. $w_3$) is the maximal contiguous subword immediately to the left (resp. right) of $a$ whose letters are all larger than $a$. Following Foata and Strehl [14] we define the action $\varphi_a$ by

Note that if $a$ is a double ascent (resp. double descent), then $w_2 = \varnothing$ (resp. $w_3 = \varnothing$), and if $a$ is a peak then $w_2 = w_3 = \varnothing$. For instance, if $a = 3$ and $\pi = 28531746\in{\mathfrak{S}}_7$, then $w_1 = 2,w_2 = 85,w_3 = \varnothing$ and $w_4 = 1746$. Thus $\varphi_a(\pi) = 23851746$. Clearly, $\varphi_a$ is an involution acting on ${\mathfrak{S}}_n$ and it is not hard to see that $\varphi_a$ and $\varphi_b$ commute for all $a,b\in[n]$. Brändén [3] modified the map $\varphi_a$ to be

See Figure 2 for illustration, where exchanging $w_2$ and $w_3$ in the $a$-factorisation is equivalent to move $a$ from a double ascent to a double descent or vice versa. Note that the boundary condition does matter. Take the permutation $569173428$ in Figure 2 as an example. If $\pi(0) = 10$ instead, then $5$ becomes a valley and will be fixed by $\varphi'_5$.

It is clear that $\varphi'_a$'s are involutions and commute. For any subset $S\subseteq[n]$ we can then define the map $\varphi'_S :{\mathcal{DP}}_{2n+1}\rightarrow{\mathcal{DP}}_{2n+1}$ by

Note that $\varphi'_{2n+1}(\pi) = \pi$ and the concatenation of $\varphi'_{2a-1}(\pi)\varphi'_{2a}(\pi)$ is closed for $\pi\in{\mathcal{DP}}_{2n+1}$. Hence the group ${\mathbb{Z}}_2^{n}$ acts on ${\mathcal{DP}}_{2n+1}$ via the functions $\varphi'_S$, $S\subseteq[n]$. This action will be called the Modified Foata–Strehl action (MFS-action for short).

Proof of Theorem 1. For any permutation $\pi\in{\mathcal{DP}}_{2n+1}$, let ${\mathsf{Orb}}(\pi) = \{g(\pi): g\in{\mathbb{Z}}_2^{n}\}$ be the orbit of $\pi$ under the MFS-action. The MFS-action divides the set ${\mathcal{DP}}_{2n+1}$ into disjoint orbits. Moreover, for $\pi\in {\mathcal{DP}}_{2n+1}$, $2a-1$ and $2a$ are double descents (resp. double ascents) of $\pi$ if and only if $2a-1$ and $2a$ are double ascents (resp. double descents) of $\varphi'_{2a-1}(\pi)\varphi'_{2a}(\pi)$. Double descents (resp. double ascents) $2a-1$ and $2a$ of $\pi$ remains a double descent (resp. double ascent) of $\varphi'_{2b-1}(\pi)\varphi'_{2b}(\pi)$ for any $b\neq a$. Hence, there is a unique permutation in each orbit which has no double descent. Let $\bar\pi$ be this unique element in ${\mathsf{Orb}}(\pi)$, then ${\mathsf{da}}\:\bar{\pi} = 2n+1-{\mathsf{pk}}\:\bar{\pi}-{\mathsf{val}}\:\bar{\pi}$ and ${\mathsf{des}}\:\bar{\pi} = {\mathsf{pk}}\:\bar{\pi}-1 = {\mathsf{val}}\:\bar{\pi}$. And for any other $\pi'\in{\mathsf{Orb}}(\pi)$, it can be obtained from $\bar{\pi}$ by repeatedly applying $\varphi'_{2a-1}$ and $\varphi'_{2a}$ for some double ascents $2a-1$ and $2a$ of $\bar{\pi}$. Once $\varphi'_{2a-1}\varphi'_{2a}$ is used, $\frac{{\mathsf{des}}}{2}$ increases by $1$ and $\frac{{\mathsf{da}}}{2}$ decreases by $1$. Thus

By summing over all the orbits that compose together to form ${\mathcal{DP}}_{2n+1}$, we obtain

by transforming $x$ to $x^2$, (23) is derived immediately.

6.   Proof of Theorem 2.9 and Theorem 2.10

We need the following result[16,Lemma 2.1].

Lemma 6.1 (Shin-Zeng). For $\sigma\in{\mathfrak{S}}_n$, we have

and

As ${\mathsf{exc}} = {\mathsf{cval}}+{\mathsf{cda}}$, ${\mathsf{des}} = {\mathsf{lpk}}+{\mathsf{ldd}} = {\mathsf{lval}}+{\mathsf{ldd}}$, by Lemma 6.1 and Definition 2.8, we obtain the following result.

Theorem 6.2. Let $\widetilde{\Phi}$ be the restriction of $\Phi$ on ${\mathcal{LDP}}_{2n}$. Then $\widetilde{\Phi}$ is a bijection from ${\mathcal{LDP}}_{2n}$ to ${\mathcal{CDP}}_{2n}$. Moreover, for $\sigma\in{\mathcal{LDP}}_{2n}$, we have

Proof of Theorem 2.9. Using Foata-Zeilberger's bijection $\Psi_{FZ} : {\mathcal{CDP}}_{2n} \to {\mathfrak{DH}}_{2n}^*$, the restricted doubled Laguerre history $(s_{0}, \ldots, s_{2n}, p_{1},\ldots, p_{2n})$ is constructed as follows. Define $s_{0} = (0,0)$ and

● the step $(s_{i-1}, s_{i})$ is North-East if $i$ is a cyclic valley,

● the step $(s_{i-1}, s_{i})$ is South-East if $i$ is a cyclic peak,

● the step $(s_{i-1}, s_{i})$ is East blue if $i$ is a double drop (or fixed point),

● the step $(s_{i-1}, s_{i})$ is East red if $i$ is a double excedance,

while $p_{i} = {\mathsf{nest}}_{i}\,\sigma$ for $i = 1,\ldots, 2n$. Then, we have

Thus $(s_{0}, \ldots, s_{2n}, p_{1},\ldots, p_{2n})$ is a restricted doubled Laguerre history of length $2n$ and

where ${\rm{NE}} \gamma$, ${\rm{EB}} \gamma$, and ${\rm{ER}}\gamma$ are the number of North-East steps, East blue steps, and East red steps of $\gamma$ and ${\rm{EB}}^* \gamma$ is the number of East blue steps whose height is equal to $p_i$. Given a doubled path $\gamma$, the weight of each step at height $k$ is created by using the following rules:

if the step is North-East, East blue, East red and South-East, respectively, and the weight of $\gamma$ is defined to be the product of the step weights. Summing over all the doubled paths of length $2n$ with the rules (51), we have

By Lemma 3.1, $J_{2n}(p,q,x,u,v,w, y)$ are the coefficients in the following continued fraction expansion,

By transforming $z$ to $-z^2$ in (53), we obtain (24) immediately. This completes the proof of (26). This lead to (25) combining (50) and (26).

Proof of Theorem 2.10. The generating function of the right side of Eq. (32) is

where $\widetilde{{\mathcal{DD}}}_{2n}: = \cup_{k = 0}^n{\mathcal{DD}}_{2n, 2k, 0}.$ Using Theorem 2.9, we have

Eq. (53) implies that

Making the substitution $z\mapsto(q^2u^2+x^2v^2)z$ and $w\mapsto xw/(q^2u^2+x^2v^2)$ in the above equation, we obtain the continued fraction of (55) is

which is generating function of $\sum_{n\geq0} J_{2n}(p, q, x, u, v, w, 0)z^{n}$ by (53). This completes the proof.

7.   Proof of Theorem 2.11

We need the following lemma. Let

Lemma 7.1. [23,Eq. (41)] We have

Define $D_{2n}^{cyc}(\beta, x, u, v, w)$ to be the coefficients in the following continued fraction expansion

where, for $k\geq 0$,

Lemma 7.2. We have

Proof of Lemma 7.2. Comparing the definition of (57) and (60), observing the Eq. (58), we constuct a doubled path $\gamma$, the weight is created by using the following rules:

where $a_k$ (resp. $b_k$, $b'_k$ and $c_k$) is the weight of North-East (resp. East blue, East red and South-East) step at height $k$. The weight of $\gamma$ is defined to be the product of the step weights. Summing over all the doubled paths of length $2n$ with the rules (61), we have

By Lemma 3.1, $D_{2n}^{{\mathsf{cyc}}}(\beta,x,u,v,w)$ are the coefficients in the following continued fraction expansion,

which is equivalent to (59) by transforming $z$ to $(-z)^2$.

Proof of Thereom 2.11. Then the generating function of the right side of Eq. (34) is

Using Lemma 7.2, we have

Eq. (62) implies that

Making the substitution $z\mapsto(1+x^2)z$ and $w\mapsto x/(1+x^2)$ in the above equation, we obtain the continued fraction of (64) is

which is generating function of $1+\sum_{n\geq1} D_{2n}^{{\mathsf{cyc}}}(\beta, x, 1, 1,1)z^{n}$ by (62). This completes the proof.

8.   The alternating permutations and Jacobi elliptic functions

A permutation $\sigma = \sigma_1\sigma_2\cdots \sigma_n\in {\mathfrak{S}}_n$ is alternating (resp. falling alternating) permutation if $\sigma_1<\sigma_2$, $\sigma_2>\sigma_3$, $\sigma_3<\sigma_4$, etc. (resp. $\sigma_1>\sigma_2$, $\sigma_2<\sigma_3$, $\sigma_3>\sigma_4$, etc.). Let ${\mathfrak{A}}_n^*$ (resp. ${\mathfrak{A}}_n$) be the set of alternating (resp. falling alternating) permutations on $[n]$. Let ${\mathsf{eval}}\,\pi$ (resp. ${\mathsf{oval}}$) and ${\mathsf{opk}}\,\pi$ (resp. ${\mathsf{epk}}$) denote the number of even valleys (resp. odd valleys) and odd peaks of $\pi$ (resp. even peaks).

A Dyck path is a Motzkin path without horizontal step. So the length of a Dyck path must be even. Let ${{Dyck}}_{2n}$ denote the set of Dyck paths of length ${2n}$. Then, it is well known (see [12]) that

Recall Definition 3.2, let Dyck path diagram (resp. restricted Dyck path diagram) of length $2n$ be the Lagurre history (restriced Laguerre history) of length $2n$ without east steps. Denote by ${\mathcal{P}}_{2n}$ (resp. ${\mathcal{P}}^*_{2n}$) the set of Dyck path diagram (restricted Dyck path diagram) of length $2n$. There are several well-known bijections between ${\mathfrak{A}}_{2n}$ and ${\mathcal{P}}_{2n-1}$ and ${\mathcal{P}}^*_{2n}$, see [22] and references therein.

We also need a standard contraction formula for continued fractions, see [22,Eq. (44)].

Lemma 8.1 (Contraction formula). There holds

Define the polynomials $E_{n}(p, q, x, y)$ by the continued fraction expansions

and

We have the following combinatorial interpretations for $E_{n}(p, q, x, y)$.

Theorem 8.2. For $n\geq 0$, we have

Proof. We prove the Eq. (70) and Eq. (71) by using Françon-Viennot's bijection $\Psi_{FV}: {\mathfrak{A}}_{2n+1}\to {\mathcal{P}}_{2n}$ and $\Psi^*_{FV}: {\mathfrak{A}}_{2n}\to {\mathcal{P}}^*_{2n}$. For $\sigma\in{\mathfrak{A}}_{2n+1}$, the corresponding Dyck path diagram $(s_{0}, \ldots, s_{2n}, \xi_{1},\ldots, \xi_{2n})$ is constructed as follows: Let $s_{0} = (0,0)$ and for $i = 1, \ldots, 2n$,

● the step $(s_{i-1}, s_{i})$ is North-East if $i$ is a valley,

● the step $(s_{i-1}, s_{i})$ is South-East if $i$ is a peak.

While $\xi_{i} = ({31\text{-}2})_{i}\sigma$ for $i = 1,\ldots, 2n$. We only prove Equation (70) and leave (71) to the interested reader.

For any $\sigma = \sigma_1\sigma_2\ldots\sigma_{2n}\in {\mathfrak{A}}_{2n}$, let $\sigma^* = \sigma_1\sigma_2\ldots\sigma_{2n}\sigma_{2n+1}$ with $\sigma_{2n+1} = 2n+1$. Let $\Psi^*_{FV}(\sigma): = \Psi_{FV}(\sigma^*)$. Since 1 is the valley then $({31\text{-}2})_1\sigma + ({2\text{-}31})_1\sigma = 0 = h_1$, and for $i>1$,

by induction we have

Therefore,

where ${\rm{NE}}\, \gamma$, ${\rm{ SE}}\, \gamma$, ${\rm{ENE }}\, \gamma$, ${\rm{ONE }}\,\gamma$, ${\rm{ ESE}}\,\gamma$ and ${\rm{ OSE}}\, \gamma$ are the number of North-East steps, South-East steps, North-East steps at even positions, North-East steps at odd positions, South-East steps at even positions, and South-East steps at odd positions. By inductions it is easy to see that the the height $h_{2i}$ (resp. $h_{2i'+1}$) of even step $(s_{2i-1}, s_{2i})(1\leq i\leq n)$ (resp. odd step $(s_{2i'}, s_{2i'+1})(0\leq i'\leq n-1)$) of Dyck path is odd (resp. even). For example, $\sigma = \,645231$ gives the path $({\rm{ONE}},{\rm{ ENE}},{\rm{ OSE}},{\rm{ ENE}},{\rm{ OSE}},{\rm{ ESE}})$ and the weight $(y, xp, xq, xp, xq, y)$. Let $[n]_{p,q} = (p^n-q^n)/(p-q)$, given a Dyck path $\gamma$, the weight of each step is created by using the following rules:

if the step is North-East at height $2k$, North-East at height $2k+1$, South-East at height $2k$, and South-East at height $2k+1$, respectively, and the weight of $\gamma$ is defined to be the product of the step weights. Summing over all the doubled paths of length $2n$ with the rules (72), we have

By (67), $J_{2n}(p,q,x,y)$ are the coefficients in the following continued fraction expansion,

By transforming $z^2$ to $-z^2$ for the above equation, we obtain (68) immediately, This completes the proof of Eq. (70).

Remark 2. By Lemma 8.1 it is easy to check that

Given a Dyck path ${{Dyck}}_{2n}$, a North-East step at positions $(s_{2i-1}, s_{2i})(1\leq i\leq n)$ is matched by some South-East step at $(s_{2i'}, s_{2i'+1})(0\leq i\leq n-1)$, i.e., the number of North-East even steps is equal to the number of South-East odd steps. From the Françon-Viennot's bijection, the number of even valleys is equal to the number of odd peaks for $\pi\in {\mathfrak{A}}_{2n}$. Therefore, when $p = q = 1$, (70) reduces to Flajolet's result [12,Theorem 4].

2. When $x = y = 1$, (70) and (71) reduce to Shin-Zeng's result [22,Theorem 4].

3. Dumont [10,Propostion 7] obtained $E_{2n}(1, 1, x, y)$ by enumerating cycle-alternating permutations with distinct weights for even and odd cycle peaks. Further refinements of $E_{2n}(p, q, x, y)$ were given in [25,Section 2.15] with combinatorial interpretations in terms of cycle-alternating permutations.

Acknowledgments

The author thanks Prof. Jiang Zeng for his inspiring discussions and useful comments. Most of the present work was done during his PhD at Institut Camille Jordan, Université Claude Bernard Lyon 1 in 2018-2019.