We introduce a parity–sum statistic on permutations that assigns to each position a weight determined by the parity of the entry occupying it. When restricted to alternating permutations, this statistic yields two \(q\)–analogues of the Euler numbers, corresponding to the up–down and down–up types. We establish symmetry and reciprocity properties of these polynomials. Specializing at \(q=1\), the resulting recursions reduce to the classical enumerative relations and recover Andr’e’s convolution identity for the Euler numbers. The distribution of the parity–sum statistic over the full symmetric group is also determined.
Let \(\mathrm{Alt}^{\uparrow\downarrow}(n)\) and \(\mathrm{Alt}^{\downarrow\uparrow}(n)\) denote the sets of up–down and down–up alternating permutations of \([n]\), respectively. The Euler numbers are defined by \[\label{eq:edef} E_n = |\mathrm{Alt}^{\uparrow\downarrow}(n)| = |\mathrm{Alt}^{\downarrow\uparrow}(n)|. \tag{1}\]
This sequence (A000111 in the OEIS [4]) starts with \[1 , ~1 , ~1 , ~2 , ~5 , ~16 , ~61 , ~272, ~1385, ~ 7936, \ldots\]
The Euler numbers satisfy André’s convolution identity [1, 2] \[\label{eq:andre} 2E_{n} = \sum_{k=0}^{n-1} \binom{n-1}{k}\,E_k\,E_{n-k-1}. \tag{2}\]
Equivalently, their exponential generating function is given by \[\label{eq:sectan} \sum_{n\ge 0} E_n\,\frac{x^n}{n!} = \sec x + \tan x , \tag{3}\] whose decomposition into even and odd parts yields the classical generating functions for the secant and tangent numbers.
A beautiful \(q\)–refinement of André’s theory was developed by Stanley ([5], [6], [7, Section 1.4]). Stanley proved properties of his \(q\)–analogues via \(q\)–trigonometric functions, which provide a \(q\)–analogue of André’s convolution itself. The inversion \(q\)–analogues are defined by \[\label{eq:inve} E_n(q) = \sum_{\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)} q^{\mathrm{inv}(\sigma)}, \qquad E^*_n(q) = \sum_{\sigma\in\mathrm{Alt}^{\downarrow\uparrow}(n)} q^{\mathrm{inv}(\sigma)}. \tag{4}\]
The enumerators in (4) are related by the reciprocity relation \[\label{eq:rec} E^*_n(q) = q^{\binom{n}{2}}\,E_n(q^{-1}). \tag{5}\]
The present paper considers the parity–sum statistic on permutations and the associated \(q\)–polynomials obtained by using this weight on alternating permutations. Although it is distinct from the inversion number, the resulting polynomials exhibit structural properties similar to those of Stanley’s inversion enumerators, including reciprocity relations. As an example, the two \(q\)–analogues \(F_n(q)\) and \(G_n(q)\) defined in (16) satisfy \[G_n(q)= \begin{cases} q^{n^2}\,F_n\!\left(q^{-1}\right), & \text{if $n$ is even},\\[2mm] q^{n^2-1}\,F_n\!\left(q^{-1}\right), & \text{if $n$ is odd}, \end{cases}\] and for odd \(n\), we have the self–reciprocity \(F_n(q) = q^{n^2-1}F_n(q^{-1})\). The recursions for \(F_n(q)\) and \(G_n(q)\) recover André’s convolution identity for \(q=1\).
Definition 2.1. Let \(S\) be a finite set of positive integers with \(|S|=n\). A permutation \(\sigma=(\sigma_1, \sigma_2, \ldots, \sigma_n)\) of \(S\) is up–down alternating, denoted \(\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(S)\) if \[\sigma_1<\sigma_2>\sigma_3<\sigma_4>\cdots,\] \(\sigma\) is down–up alternating, denoted \(\sigma\in\mathrm{Alt}^{\downarrow\uparrow}(S)\) if \[\sigma_1>\sigma_2<\sigma_3>\sigma_4<\cdots.\]
For \(S=[n]=\{1,2,\dots,n\}\) we write \(\mathrm{Alt}^{\uparrow\downarrow}(n)=\mathrm{Alt}^{\uparrow\downarrow}([n])\) and \(\mathrm{Alt}^{\downarrow\uparrow}(n)=\mathrm{Alt}^{\downarrow\uparrow}([n])\).
The Euler numbers \(E_n\) are defined by (1). They satisfy André’s classical convolution identity (2) for \(n \geq 2\) with \(E_0 = E_1 = 1\).
Stanley’s inversion refinement \(E_n(q)\) of Euler numbers and its companion \(E^*_n(q)\) are defined as in (4). Stanley showed that the exponential generating functions of can be written in terms of the \(q\)–trigonometric functions as follows (see [5, Corollary 3.3 and p. 350], [6, Theorem 2.1]): \[\label{eq:qanal} \sum_{n\ge0} E_n(q)\,\frac{x^n}{[n]_q!} = \frac{1}{\displaystyle\sum_{m\ge0}(-1)^m\frac{x^{2m}}{[2m]_q!}} ~+~ \frac{\displaystyle\sum_{m\ge0}(-1)^m\frac{x^{2m+1}}{[2m+1]_q!}}{\displaystyle\sum_{m\ge0}(-1)^m\frac{x^{2m}}{[2m]_q!}}, \tag{6}\] where \([n]_q!=(1+q)(1+q+q^2) \cdots (1+q+ \cdots + q^{n-1})\) with \([0]_q!=1\).
Stanley’s results give a generalization of (3) and also a \(q\)–analogue of André’s convolution (2) in the form \[\label{eq:qandre} E_n(q) + E^*_n(q) = \sum_{k=0}^{n-1} q^k \binom{n-1}{k}_q E_k (q) E^*_{n-1-k} (q) \qquad (n \geq 2). \tag{7}\]
Definition 3.1. For \(\sigma\in S_n\), define \[\label{eq:L} L_n(\sigma) = \sum_{j=1}^{n} \begin{cases} j, & \text{if $\sigma_j$ is even},\\[2mm] n-j, & \text{if $\sigma_j$ is odd}. \end{cases} \tag{8}\]
\(L_n(\sigma)\) can be viewed as assigning to each position \(j\) a weight measured from the left end if \(\sigma_j\) is even, and a complementary weight measured from the right end of the index set if \(\sigma_j\) is odd.
As a positional statistic, \(L_n(\cdot)\) is naturally associated with alternating permutations whose valleys and peaks occur at positions of fixed parity among \(1, 2, \ldots, n\). This structural property is reflected in the alternating sum appearing in the formula for \(L_n (\sigma)\) given in Lemma 3.2 below.
Lemma 3.2. For \(\sigma=(\sigma_1, \sigma_2, \ldots, \sigma_n)\in S_n\) we have \[L_n(\sigma)=C_n+\sum_{j=1}^n j\,(-1)^{\sigma_j},\] where \(C_{2m}=2m^2\) and \(C_{2m+1}=(2m+1)(m+1)\).
Proof. Fix \(n\ge1\) and \(\sigma\in S_n\). Write \(s_j=(-1)^{\sigma_j}\). The \(j\)th summand in (8) equals \(j\) when \(s_j=+1\) and equals \(n-j\) when \(s_j=-1\). This can be written uniformly as \[\frac{n}{2}+\Bigl(j-\frac{n}{2}\Bigr)s_j.\]
Summing over \(j=1, 2, \dots,n\) yields \[\label{eq:L-signed-expand} L_n(\sigma) = \frac{n^2}{2} +\sum_{j=1}^n j\,s_j -\frac{n}{2}\sum_{j=1}^n s_j. \tag{9}\]
Because \(\sigma\) is a permutation of \([n]\), the last sum depends only on \(n\): \[\sum_{j=1}^n s_j = \begin{cases} 0,& n=2m,\\ -1,& n=2m+1. \end{cases}\]
Substituting into (9) proves the lemma with the stated constants \(C_n\). ◻
Example 3.3. Let \(n=5\) and \(\sigma=(2,5,1,4,3)\in\mathrm{Alt}^{\uparrow\downarrow}(5)\). Using the definition and also the equivalent formulation of Lemma 3.2, we have \[L_5(\sigma)= 1+3+2+4+0=15+1-2-3+4-5=10.\]
Example 3.4. Let \(n=6\) and \(\sigma=(5,3,4,1,6,2)\in\mathrm{Alt}^{\downarrow\uparrow}(6)\). Then \[L_6(\sigma)=5+4+3+2+5+6 = 18-1-2+3-4+5+6 = 25.\]
It turns out that the parity of \(L_n(\sigma)\) is independent of \(\sigma\).
Lemma 3.5. For every \(n\ge 1\) and every \(\sigma\in S_n\), \[(-1)^{L_n(\sigma)}= \begin{cases} (-1)^m, & \text{if } n=2m,\\[1mm] 1, & \text{if } n=2m+1. \end{cases}\]
Proof. By Lemma 3.2, \[L_n(\sigma)=C_n+\sum_{j=1}^n j\,(-1)^{\sigma_j}.\]
Since \((-1)^{\sigma_j}\equiv 1\pmod 2\) for all \(j\), we obtain \[L_n(\sigma)\equiv C_n+\frac{n(n+1)}2 \pmod 2.\]
If \(n=2m\), then \[C_{2m}+\frac{(2m)(2m+1)}2 =4m^2+m\equiv m\pmod 2,\] so \((-1)^{L_n(\sigma)}=(-1)^m\). If \(n=2m+1\), then \[C_{2m+1}+\frac{(2m+1)(2m+2)}2 =2(2m+1)(m+1)\equiv 0\pmod 2,\] and hence \((-1)^{L_n(\sigma)}=1\). ◻
For \(0\le k\le n\), the \(q\)–binomial coefficient is defined by \[\binom{n}{k}_q = \frac{(1-q^n)(1-q^{n-1})\cdots(1-q^{n-k+1})}{(1-q)(1-q^2)\cdots(1-q^k)}.\]
We have the following standard subset–sum identity.
Lemma 4.1. \[\label{eq:q-binomial} \sum_{\substack{S\subseteq[n]\\ |S|=k}} q^{\sum_{j\in S} j} = q^{\binom{k+1}{2}}\binom{n}{k}_{q} . \tag{10}\]
We briefly consider the distribution of \(L_n(\sigma)\) over all permutations. For \(n\ge 0\) define \[\label{def:An} A_n(q)=\sum_{\sigma\in S_n} q^{L_n(\sigma)} . \tag{11}\]
Theorem 4.2. Suppose \(L_n\) and \(A_n(q)\) are as defined in (8) and (11). Then \[ A_{2m}(q) = (m!)^2\,q^{m^2}\binom{2m}{m}_{q^2},\ \tag{12}\] \[ A_{2m+1}(q) = m!(m+1)!\,q^{m(m+1)}\binom{2m+1}{m}_{q^2}. \ \tag{13}\]
Proof. We give the derivation in the even case \(n=2m\). The proof of the expression for the odd case follows similar steps with minor modifications of the formulas derived in the even case.
For \(\sigma\in S_{2m}\) let \[S(\sigma)=\{\, j\in[2m] : \sigma_j \text{ is even}\,\}.\]
We have \(|S(\sigma)|=m\) for all \(\sigma\). Fix a subset \(S\subseteq[2m]\) with \(|S|=m\). If \(S(\sigma)=S\), then the even values can be arranged among the positions in \(S\) in \(m!\) ways and the odd values among the complementary positions in \(m!\) ways. Hence \[\label{eq:Sn-factor-even} A_{2m}(q)=(m!)^2\sum_{\substack{S\subseteq[2m]\\ |S|=m}} q^{L_{2m}(S)}, \tag{14}\] where \(L_{2m}(S)\) denotes the common value of \(L_{2m}(\sigma)\) over all \(\sigma\) with \(S(\sigma)=S\).
By Lemma 3.2, for any such \(\sigma\) we have \[L_{2m}(\sigma)=2m^2+\sum_{j=1}^{2m} j\,(-1)^{\sigma_j}.\]
When \(S(\sigma)=S\), we have \((-1)^{\sigma_j}=+1\) for \(j\in S\) and \((-1)^{\sigma_j}=-1\) for \(j\notin S\), so \[\sum_{j=1}^{2m} j\,(-1)^{\sigma_j} = \sum_{j\in S} j-\sum_{j\notin S} j = 2\sum_{j\in S} j-\sum_{j=1}^{2m} j = 2\sum_{j\in S} j-m(2m+1).\]
Therefore \[L_{2m}(S)=2m^2+2\sum_{j\in S} j-m(2m+1)=2\sum_{j\in S} j-m.\]
Substituting into (14) gives \[A_{2m}(q)=(m!)^2\,q^{-m}\sum_{\substack{S\subseteq[2m]\\ |S|=m}} (q^2)^{\sum_{j\in S} j}.\]
The subset–sum identity (10) of Lemma 4.1 with \(n=2m\), \(k=m\), and \(q\) replaced by \(q^2\) yields \[A_{2m}(q) =(m!)^2\,q^{-m}\,(q^2)^{\binom{m+1}{2}}\binom{2m}{m}_{q^2} =(m!)^2\,q^{m^2}\binom{2m}{m}_{q^2}.\] ◻
We extend the notation \(L_n(\cdot)\) to words of length \(m\le n\) by the same positional rule as in (8). For the definition of this notation to be unambiguous, we assume that we are working with a fixed underlying length \(n\).
Definition 5.1. Let \(n\ge 1\). For a word \(\sigma=\sigma_1\sigma_2\cdots\sigma_m\) of length \(m\le n\) with entries in the positive integers, define \[\label{eq:ambient-weight} L_n(\sigma) = \sum_{j=1}^{m} \begin{cases} j, & \text{if $\sigma_j$ is even},\\ n-j, & \text{if $\sigma_j$ is odd}. \end{cases} \tag{15}\]
Definition 5.2. Let \(n\ge 1\). For any finite set \(S\) with \(|S|=m\le n\), define \[F^{\uparrow\downarrow}_{S,n}(q) = \sum_{\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(S)} q^{L_n(\sigma)}, \qquad F^{\downarrow\uparrow}_{S,n}(q) = \sum_{\sigma\in\mathrm{Alt}^{\downarrow\uparrow}(S)} q^{L_n(\sigma)}.\]
When \(S=[n]\), write \[\label{eq:star} F_n(q)=F^{\uparrow\downarrow}_{[n],n}(q)=\sum_{\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)} q^{L_n(\sigma)}, \qquad G_n(q)=F^{\downarrow\uparrow}_{[n],n}(q)=\sum_{\sigma\in\mathrm{Alt}^{\downarrow\uparrow}(n)} q^{L_n(\sigma)}. \tag{16}\]
Next we add one more parameter and extend Definition 5.1:
Definition 5.3. Let \(n\ge 1\) and let \(s\ge 0\). For a word \(\tau=\tau_1 \tau_2 \cdots\tau_m\) of length \(m\), define \[\label{eq:shifted-weight} L_{n,s}(\tau) := \sum_{j=1}^{m} \begin{cases} s+j, & \text{if $\tau_j$ is even},\\ n-(s+j), & \text{if $\tau_j$ is odd}. \end{cases} \tag{17}\]
Note that \(L_{n, 0}(\tau)=L_n(\tau)\) for words \(\tau\) of length \(m\le n\).
For a finite set \(R\) with \(|R|=m\), define shifted set–refined polynomials \[F^{\uparrow\downarrow,(s)}_{R,n}(q) = \sum_{\tau\in\mathrm{Alt}^{\uparrow\downarrow}(R)} q^{L_{n,s}(\tau)}, \qquad F^{\downarrow\uparrow,(s)}_{R,n}(q) = \sum_{\tau\in\mathrm{Alt}^{\downarrow\uparrow}(R)} q^{L_{n,s}(\tau)}.\]
Remark 5.4. We use the definitions above to avoid standardization. This seems essential because the statistic \(L_n\) depends on the parity of the values, which is not preserved under standardization.
Lemma 6.1. Let \(n\ge 2\) and \(\sigma\in \mathrm{Alt}^{\uparrow\downarrow}(n)\sqcup \mathrm{Alt}^{\downarrow\uparrow}(n)\). Then \(\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)\) if and only if the entry \(1\) occurs in an odd position.
Proof. In an up–down permutation, positions \(1,3,5,\dots\) are local minima (valleys) and positions \(2,4,6,\dots\) are local maxima (peaks). The minimum value \(1\) cannot occur at a peak, hence it must occur in an odd position. The down–up case is analogous, with valleys and peaks interchanged. ◻
Theorem 6.2. Let \(n\ge 1\) and set \(T=\{2,3,\dots,n\}\).
(a) Up–down recursion \[\label{eq:UD-recursion} F_n(q) = \sum_{\substack{0\le k\le n-1\\ k\ \mathrm{even}}} q^{\,n-1-k} \sum_{\substack{S\subseteq T\\ |S|=k}} F^{\uparrow\downarrow}_{S,n}(q)\; F^{\downarrow\uparrow,(k+1)}_{T\setminus S,n}(q). \tag{18}\]
(b) Down–up recursion \[\label{eq:DU-recursion} G_n(q) = \sum_{\substack{0\le k\le n-1\\ k\ \mathrm{odd}}} q^{\,n-1-k} \sum_{\substack{S\subseteq T\\ |S|=k}} F^{\downarrow\uparrow}_{S,n}(q)\; F^{\uparrow\downarrow,(k+1)}_{T\setminus S,n}(q). \tag{19}\]
Proof. We prove (18). The proof of (19) is similar, using Lemma 6.1 for the down–up case.
Fix \(\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)\). Suppose \(1\) is in position \(k+1\). By Lemma 6.1, \(k\) is even and \(0\le k\le n-1\). Define \(S\) to be the set of values of \(\sigma\) appearing to the left of \(1\). Then \(S\subseteq T\) and \(|S|=k\). The left block \[\alpha=\sigma_1\sigma_2\cdots\sigma_k,\] is a permutation of \(S\). Since \(\sigma\) is up–down and \(k\) is even, the pattern within positions \(1,2,\dots,k\) is up–down, so \(\alpha\in\mathrm{Alt}^{\uparrow\downarrow}(S)\).
Let \(R=T\setminus S\) be the set of entries to the right of \(1\), and let \[\beta=\sigma_{k+2}\sigma_{k+3}\cdots\sigma_{n},\] be the right block. \(\beta\) is a permutation of \(R\) of length \(n-1-k\). Because \(k\) is even, the position \(k+2\) is even, hence \(\sigma_{k+2}\) is a peak in the up–down pattern. Therefore when the right block is reindexed locally as positions \(1,2,\dots,n-1-k\), its inequalities are down–up, i.e. \(\beta\in\mathrm{Alt}^{\downarrow\uparrow}(R)\).
Conversely, given an even \(k\), a subset \(S\subseteq T\) of size \(k\), an up–down permutation \(\alpha\in\mathrm{Alt}^{\uparrow\downarrow}(S)\), and a down–up permutation \(\beta\in\mathrm{Alt}^{\downarrow\uparrow}(T\setminus S)\), concatenation \[\sigma=\alpha\;1\;\beta,\] produces an element of \(\mathrm{Alt}^{\uparrow\downarrow}(n)\) with \(1\) in position \(k+1\). Thus we have a bijection between such \(\sigma\) and quadruples \((k,S,\alpha,\beta)\).
We now verify the factorization of the \(q\)–weight by proving the identity \[\label{eq:q-weight} L_n(\alpha\,1\,\beta)\;=\;L_n(\alpha)\;+\;\bigl(n-(k+1)\bigr)\;+\;L_{n, k+1}(\beta), \qquad (|\alpha|=k). \tag{20}\]
Write \(\sigma=\alpha\,1\,\beta\) with \(\alpha=\sigma_1\cdots\sigma_k\) and \(\beta=\sigma_{k+2}\cdots\sigma_n\) as above. We split the defining sum of \(L_n(\sigma)\) into the contributions from positions \(1,2, \dots,k\), the position \(k+1\), and positions \(k+2,\dots,n\). The left block contributes \(L_n(\alpha)\) since its letters occupy the same global positions \(1,2,\dots,k\), so the contribution of \(\alpha\) to \(L_n(\sigma)\) is exactly \(L_n(\alpha)\).
The entry \(1\) is odd and occurs at position \(k+1\), its contribution to \(L_n(\sigma)\) is \[n-(k+1)=n-1-k.\]
For the right block, the \(t\)-th letter of \(\beta\) (locally at position \(t\)) occupies global position \(k+1+t\) in \(\sigma\), so its contribution uses the shifted indices \(k+1+t\) in \(\sigma\) with shift \(s= k+1\). This is exactly \(L_{n, k+1}(\beta)\) by (17). Adding these three contributions proves (20).
Summing over all \((k,S,\alpha,\beta)\) gives the three factors \(F^{\uparrow\downarrow}_{S,n}(q)\), \(q^{n-1-k}\) and \(F^{\downarrow\uparrow,(k+1)}_{T\setminus S,n}(q)\) of the identity (18). ◻
Corollary 6.3. Let \(n\ge 1\) and set \(T=\{2,3,\dots,n\}\). Then \[\label{eq:H-star} F_n(q)+G_n(q) = \sum_{k=0}^{n-1} q^{\,n-1-k} \sum_{\substack{S\subseteq T\\ |S|=k}} \begin{cases} F^{\uparrow\downarrow}_{S,n}(q)\; F^{\downarrow\uparrow,(k+1)}_{T\setminus S,n}(q), & \text{if $k$ is even},\\[3mm] F^{\downarrow\uparrow}_{S,n}(q)\; F^{\uparrow\downarrow,(k+1)}_{T\setminus S,n}(q), & \text{if $k$ is odd}. \end{cases} \tag{21}\]
Proof. This follows by adding (18) and (19). ◻
Remark 6.4. Define, for \(m\ge 0\), \[\varepsilon(m):= \begin{cases} \uparrow\downarrow,& m\ \mathrm{even},\\ \downarrow\uparrow,& m\ \mathrm{odd}, \end{cases} \qquad \overline{\varepsilon}(m)= \begin{cases} \downarrow\uparrow,& m\ \mathrm{even},\\ \uparrow\downarrow,& m\ \mathrm{odd}. \end{cases}\]
Then the identity (21) may be written as a single sum over all subsets of \(T=\{2,3,\dots,n\}\): \[F_n(q)+G_n(q) = \sum_{S\subseteq T} q^{\,n-1-|S|} \;F^{\varepsilon(|S|)}_{S,n}(q)\; F^{\overline{\varepsilon}(|S|),( |S|+1)}_{T\setminus S,n}(q).\]
This notation makes explicit that \(F_n(q)+G_n(q)\) is obtained by summing over all splittings \(T=S\sqcup(T\setminus S)\), with the alternating type of each block determined by the parity of \(|S|\).
Corollary 6.5. For \(n\ge 2\), \[F_n(1)+G_n(1)=2E_n = \sum_{k=0}^{n-1} \binom{n-1}{k}\,E_k\,E_{n-1-k}.\]
Proof. For all \(k\ge 0\) we have \(F_k(1)=G_k(1)=E_k\). Specializing Corollary 6.3 at \(q=1\) gives André’s convolution (2). ◻
Lemma 7.1. Let \(c:S_n\to S_n\) be the complement map defined by \(c(\sigma)_i = n+1-\sigma_i\), \((1\le i\le n)\). Then \(c:\mathrm{Alt}^{\uparrow\downarrow}(n) \longleftrightarrow \mathrm{Alt}^{\downarrow\uparrow}(n)\) is a bijection and \[L_n(c(\sigma))= \begin{cases} L_n(\sigma), & \text{if $n$ is odd},\\[1mm] n^2 – L_n(\sigma), & \text{if $n$ is even}. \end{cases}\]
Proof. The complement map \(c\) reverses all inequalities, hence it is a bijection \(\mathrm{Alt}^{\uparrow\downarrow}(n)\leftrightarrow \mathrm{Alt}^{\downarrow\uparrow}(n)\).
Let \(\tau=c(\sigma)\). Then \(\tau_j=n+1-\sigma_j\), and if \(n\) is odd, then \((-1)^{\tau_j}=(-1)^{\sigma_j}\) for all \(j\). Hence each position contributes the same weight to \(L_n(\tau)\) as it does to \(L_n(\sigma)\) and \(L_n(c(\sigma))=L_n(\sigma)\). If \(n\) is even, then \((-1)^{\tau_j}=-(-1)^{\sigma_j}\), so that \[\label{eq:square} \sum_{j=1}^n j\,(-1)^{\sigma_j} + \sum_{j=1}^n j\,(-1)^{\tau_j} = 0. \tag{22}\]
By Lemma 3.2 we have \[\sum_{j=1}^n j\,(-1)^{\sigma_j} = L_n(\sigma) – C_n \quad \mbox{and} \quad \sum_{j=1}^n j\,(-1)^{\tau_j} = L_n(\tau) – C_n,\] and therefore \[L_n(\sigma) + L_n(c(\sigma)) = 2 C_n.\]
The claim follows since for \(n\) even, \(2C_n = n^2\) by Lemma 3.2. ◻
Lemma 7.2. Let \(n\ge 1\) and let \(\phi:S_n\to S_n\) be the reverse–complement map \(\phi(\sigma)_i=n+1-\sigma_{n+1-i}\), \((1\le i\le n)\). Then for every \(\sigma\in S_n\), \[L_n(\phi(\sigma)) = \begin{cases} L_n(\sigma), & \text{if $n$ is even},\\[2mm] n^2-1-L_n(\sigma), & \text{if $n$ is odd}. \end{cases}\]
Proof. Let \(\tau=\phi(\sigma)\), so \(\tau_i=n+1-\sigma_{n+1-i}\). We have \[(-1)^{\tau_i} = (-1)^{n+1}\,(-1)^{\sigma_{n+1-i}}.\]
Therefore \[\begin{aligned} \nonumber \sum_{j=1}^n j\,(-1)^{\tau_j} &= (-1)^{n+1}\sum_{j=1}^n j\,(-1)^{\sigma_{n+1-j}} = (-1)^{n+1}\sum_{j=1}^n (n+1-j)\,(-1)^{\sigma_{j}}\\ \label{eq:st} &= (-1)^{n+1}\Bigl((n+1)\sum_{j=1}^n(-1)^{\sigma_{j}}-\sum_{j=1}^n j\,(-1)^{\sigma_{j}}\Bigr). \end{aligned} \tag{23}\]
Since \(\sigma\) is a permutation of \([n]\), \[\label{eq:sum} \sum_{j=1}^n(-1)^{\sigma_j}= \begin{cases} 0,& n \text{ even},\\ -1,& n \text{ odd}. \end{cases} \tag{24}\]
If \(n\) is even, then \((-1)^{n+1}=-1\) and the first term vanishes, giving \[\sum_{j=1}^{n} j\,(-1)^{\tau_j}=\sum_{j=1}^{n} j\,(-1)^{\sigma_j}.\]
Using Lemma 3.2 yields \(L_{n}(\phi(\sigma))=L_{n}(\sigma)\) in this case.
If \(n\) is odd, then from (23) and (24) \[\sum_{j=1}^{n} j\,(-1)^{\tau_j}=-(n+1)-\sum_{j=1}^{n} j\,(-1)^{\sigma_j}.\]
If \(n=2m+1\), using Lemma 3.2 with \(C_{2m+1} = (2m+1)(m+1)\) gives \[L_{n}(\phi(\sigma)) = n^2 -1 – L_{n}(\sigma),\] as claimed. ◻
We record the implications of these lemmas as a theorem.
Theorem 7.3. Let \(n\ge 1\) and define \(F_n(q)\) and \(G_n(q)\) as in (16).
(a) If \(n\) is even, then \[\label{eq:FG-even-recip} G_n(q)=q^{n^2}F_n(q^{-1}). \tag{25}\]
(b) If \(n\) is odd, then \[\label{eq:FG-odd-recip} G_n(q) = F_n(q) . \tag{26}\]
Proof. The proof uses the bijections and the weight changes in Lemmas 7.1 and 7.2. For \(n\) even \[G_n(q)= \sum_{\sigma\in\mathrm{Alt}^{\downarrow\uparrow}(n)} q^{L_n(\sigma)} = \sum_{\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)} q^{n^2-L_n(\sigma)} =q^{n^2}\sum_{\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)}(q^{-1})^{L_n(\sigma)} =q^{n^2}F_n(q^{-1}).\]
For \(n\) odd, we use the odd case of Lemma 7.1. ◻
Remark 7.4. For \(n\) odd, we also have \(G_n(q)=q^{n^2-1}F_n(q^{-1})\) by Lemma 7.2. Therefore for odd \(n\), we have the self–reciprocity property \[F_n(q) = q^{n^2-1} F_n(q^{-1}),\] which shows that in this case the coefficients of \(F_n(q)\) are symmetric.
Lemma 7.5. Define \(F_n(q)\) and \(G_n(q)\) as in (16). Then for all \(n\ge 3\), \[\deg F_n(q)= \deg G_n(q) = \left\lfloor \frac{3n^2}{4}\right\rfloor.\]
Equivalently, for \(n \geq 3\), writing \(n=2m\) or \(n=2m+1\), we have \[\deg F_{2m}(q)= \deg G_{2m}(q) = 3m^2,\qquad \deg F_{2m+1}(q)= \deg G_{2m+1} (q) = 3m(m+1).\]
Proof. First we consider the even case \(n=2m\). By definition \[F_{2m}(q)=\sum_{\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(2m)} q^{\,L_{2m}(\sigma)}.\]
For \(\sigma\in S_{2m}\) let \[S(\sigma)=\{\,j\in[2m]: \sigma_j \ \text{is even}\,\}.\]
Then \(|S(\sigma)|= m\), and from Lemma 3.2, the maximum value of \(L_{2m}\) is achieved when \(S(\sigma) = \{ m+1, m+2,\ldots , 2m\}\). For such a \(\sigma\), \[L_{2m} (\sigma) = 2m^2 + \sum_{j=m+1}^{2m} j – \sum_{j=1}^m j = 3 m^2.\]
This upper bound is achieved by the permutation \(\sigma^{\max}\in\mathrm{Alt}^{\uparrow\downarrow}(2m)\) constructed as follows.
If \(m\) is even, the first \(m\) entries of \(\sigma^{\max}\) are the odd integers \(1,3,\dots,2m-1\) arranged in alternating increasing–decreasing order, starting with \(1\), and the last \(m\) entries are the even integers \(2,4,\dots,2m\) arranged in alternating increasing–decreasing order, starting with 2. Explicitly, \[\sigma^{\max} = (1,2m-1,3,2m-3,\ldots,m+1, \hspace{2mm} 2,2m,4,2m-2,\ldots,m+2).\]
If \(m\) is odd, the first \(m\) entries of \(\sigma^{\max}\) are again the odd integers \(1,3,\dots,2m-1\) arranged in alternating increasing–decreasing order, starting with \(1\), while the last \(m\) entries are the even integers \(2,4,\dots,2m\) arranged in alternating decreasing–increasing order, starting with the largest. Explicitly, \[\sigma^{\max} = (1,2m-1,3,2m-3,\ldots,m, \hspace{2mm} 2m,2,2m-2,4,\ldots,m+1).\]
In both cases, \(\sigma^{\max}\in\mathrm{Alt}^{\uparrow\downarrow}(2m)\), the first \(m\) positions contain exactly the odd values and the last \(m\) positions contain exactly the even values. It follows that \(\deg F_{2m}(q)= 3m^2\).
For \(n=2m+1\), the maximum value of \(L_{2m+1}( \sigma)\) is achieved when the values of \(\sigma\) are even on the indices \(m+2, m+3, \ldots, 2m+1\). For such a \(\sigma\), \[L_{2m+1} (\sigma) = (2m+1)(m+1) + \sum_{j=m+2}^{2m+1} j – \sum_{j=1}^{m+1} j = 3 m(m+1).\] This upper bound is achieved by the permutation \(\sigma^{\max}\in\mathrm{Alt}^{\uparrow\downarrow}(2m+1)\) which is constructed in a fashion similar to the even case by setting
\[\sigma^{\max} = (1,2m+1,3,2m-1,\ldots,m+1, \hspace{2mm} 2m, 2,2m-2,4,\ldots,m),\] for \(m\) even and
\[\sigma^{\max} = (1,2m+1,3,2m-1,\ldots,m+2, \hspace{2mm} 2, 2m,4,2m-2,\ldots,m+1),\] for \(m\) odd.
The smallest possible value of \(L_{2m}(\sigma)\) over all \(\sigma \in S_n\) is \(m^2\), and this bound is achieved by \(\sigma^{\min}\in\mathrm{Alt}^{\uparrow\downarrow}(2m)\) defined as follows:
If \(m\) is even, set \[\sigma^{\min}= \bigl(2,2m,4,2m-2,\ldots,m+2, \hspace{2mm} 1,2m-1,3,2m-3,\ldots,m+1\bigr).\]
If \(m\) is odd, set \[\sigma^{\min}= \bigl(2,2m,4,2m-2,\ldots,m+1, \hspace{2mm} 2m-1,1,2m-3,3,\ldots , m\bigr).\]
In each case, the first \(m\) entries are the even numbers and the last \(m\) entries are the odd numbers. Thus the lowest exponent of \(F_{2m}(q)\) is \(m^2\). The lowest exponent of \(F_{2m+1}(q)\) is computed to be \(m(m+1)\).
By the even–parity reciprocity of Theorem 7.3 we obtain \[\deg G_{2m}(q)=(2m)^2-m^2=3m^2.\]
Hence \(\deg F_{2m}(q)=\deg G_{2m}(q)=3m^2\). For the odd case, we have \(\deg F_{2m+1}(q)=\deg G_{2m+1}(q)=3m(m+1)\). ◻
We calculate the first few polynomials \(F_n(q)\) and \(G_n(q)\) defined in (16) directly by constructing the alternating permutations \(\sigma\) in \(\mathrm{Alt}^{\uparrow\downarrow}(n)\) and \(\mathrm{Alt}^{\downarrow\uparrow}(n)\) and using Lemma 3.2 for the calculation of \(L_n(\sigma)\). With each example calculated for even \(n\), we verify the reciprocity properties of \(F_n(q)\) and \(G_n(q)\) given in Lemma 7.1. The degrees of the example polynomials are seen to satisfy \(\deg F_{2m}(q)= \deg G_{2m}(q) = 3m^2\) and \(\deg F_{2m+1}(q)= \deg G_{2m+1} (q) = 3m(m+1)\) as determined in Lemma 7.5.
There is only one permutation \(\sigma=(1)\), which is both up–down and down–up. So \(L_1(1)=0\) and \(F_1(q)= G_1(q) = 1\).
There is one up–down permutation \((1,2)\) with \(L_2(1,2)= 2 -1 +2 =3\), and therefore \(F_2(q)=q^3\). The down–up permutation \((2,1)\) gives \(L_2(2,1)=2 -2 +1 =1\), and therefore \(G_2(q)=q\). These satisfy \(G_2(q)=q^{4}F_2(q^{-1})\), in agreement with Lemma 7.1.
There are two up–down permutations \((1,3,2)\), \((2,3,1)\) with \(L_3(1,3,2)=6\), \(L_3(2,3,1)=2\). Since \(n\) is odd, \[F_3(q)= G_3(q) =q^2+q^6.\]
There are \(5\) alternating permutations of each type. Up–down permutations are \((1,3,2,4)\), \((1,4,2,3)\), \((2,3,1,4)\), \((2,4,1,3)\), \((3,4,1,2)\). A direct computation gives \[F_4(q)=q^{4}+2q^{8}+q^{10}+q^{12}.\]
Down–up permutations are \((2,1,4,3)\), \((3,1,4,2)\), \((3,2,4,1)\), \((4,1,3,2)\), \((4,2,3,1)\). These yield \[G_4(q)=q^4+q^6+2q^8+q^{12}.\]
Here \(F_4(q)=q^{16}G_4(q^{-1})\), in agreement with Lemma 7.1.
A longer computation with the 16 permutations of \(\mathrm{Alt}^{\uparrow\downarrow}(5)\) yields \[F_5(q) = G_5(q) = 2q^{6}+q^{8}+4q^{10}+2q^{12}+4q^{14}+q^{16}+2q^{18}.\]
Table 1 lists the inversion polynomials \(E_n(q)\) and \(E^*_n(q)\), and Table 2 lists the parity–sum polynomials \(F_n(q)\) and \(G_n(q)\) for \(1\leq n \leq 6\).
| \(n\) | \(E_n(q)=\sum q^{\mathrm{inv}(\sigma)}\) over \({\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)}\) | \(E^*_n(q)=\sum q^{\mathrm{inv}(\sigma)}\) over \({\sigma\in\mathrm{Alt}^{\downarrow\uparrow}(n)}\) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | \(1\) | \(q\) |
| 3 | \(q\!+\!q^2\) | \(q \!+\! q^2\) |
| 4 | \(q\!+\!2q^2\!+\!q^{3}\!+\!q^{4}\) | \(q^2 \!+\! q^3 \!+\! 2 q^4 \!+\! q^5\) |
| 5 | \(q^{2}\!+\!2q^3\!+\!3q^{4}\!+\!4q^{5}\!+\!3q^{6}\!+\!2q^{7}\!+\!q^{8}\) | \(q^2 \!+\! 2 q^3 \!+\! 3 q^4 \!+\! 4 q^5 \!+\! 3 q^6 \!+\! 2 q^7 \!+\! q^8\) |
| 6 | \(q^2 \!+\! 3 q^3 \!+\! 5 q^4 \!+\! 8 q^5 \!+\! 10 q^6 \!+\!\) | \(q^3 \!+\! 2 q^4 \!+\! 5 q^5 \!+\! 7 q^6 \!+\! 9 q^7 \!+\) |
| \(\qquad\)\(~~~10 q^7 \!+\! 9 q^8 \!+\!7 q^9 \!+\! 5 q^{10} \!+\! 2 q^{11} \!+\! q^{12}\) | \(\qquad\)\(~~~10 q^8 \!+\! 10 q^9 \!+\! 8 q^{10} \!+\! 5 q^{11} \!+\! 3 q^{12} \!+\! q^{13}\) |
| \(n\) | \(F_n(q)=\sum q^{L_n(\sigma)}\) over \({\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)}\) | \(G_n(q)=\sum q^{L_n(\sigma)}\) over \({\sigma\in\mathrm{Alt}^{\downarrow\uparrow}(n)}\) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | \(q^{3}\) | \(q\) |
| 3 | \(q^{2}\!+\!q^{6}\) | \(q^{2}\!+\!q^{6}\) |
| 4 | \(q^{4}\!+\!2q^{8}\!+\!q^{10}\!+\!q^{12}\) | \(q^4\!+\!q^6\!+\!2q^{8}\!+\!q^{12}\) |
| 5 | \(2q^{6}\!+\!q^{8}\!+\!4q^{10}\!+\!2q^{12}\!+\!4q^{14}\!+\!q^{16}\!+\!2q^{18}\) | \(2q^{6}\!+\!q^{8}\!+\!4q^{10}\!+\!2q^{12}\!+\!4q^{14}\!+\!q^{16}\!+\!2q^{18}\) |
| 6 | \(3 q^9 \!+\! 4 q^{11}\!+\! 4 q^{13}\!+\! 10 q^{15} \!+\! 4 q^{17} \!+\!\) | \(4 q^9 \!+\! q^{11} \!+\! 10 q^{13} \!+\! 5 q^{15} \!+\! 16 q^{17} \!+\) |
| \(\qquad\)\(~~~16 q^{19}\!+\!5 q^{21} \!+\! 10 q^{23} \!+\! q^{25} \!+\! 4 q^{27}\) | \(\qquad\)\(~~~4 q^{19} \!+\! 10 q^{21} \!+\! 4 q^{23} \!+\! 4 q^{25} \!+\! 3 q^{27}\) |
Corollary 8.1. For \(m\ge 2\), \[F_{2m}(-q)=(-1)^mF_{2m}(q),\qquad F_{2m+1}(-q)=F_{2m+1}(q),\] and the same identities hold with \(F\) replaced by \(G\).
Proof. By Lemma 3.5, \[(-q)^{L_n(\sigma)} = (-1)^{L_n(\sigma)}q^{L_n(\sigma)} = (-1)^{\,C_n+\frac{n(n+1)}2}\,q^{L_n(\sigma)}.\]
Summing over \(\sigma\in\mathrm{Alt}^{\uparrow\downarrow}(n)\) and \(\mathrm{Alt}^{\downarrow\uparrow}(n)\) yields the stated identities. ◻
As a special case of Corollary 8.1 we have for \(n\ge 1\), \[\label{eq:special} F_n(-1)=G_n(-1)= \begin{cases} (-1)^m\,E_{2m}, & n=2m,\\[2mm] E_{2m+1}, & n=2m+1, \end{cases} \tag{27}\] where \(E_n\) denotes the \(n\)th Euler number. In contrast to (27), Stanley’s inversion enumerator \(E_n(q)\) specializes to \[E_{2m}(-1)=1, \qquad E_{2m+1}(-1)=0 \quad (m\ge1).\]
These can be obtained by manipulating (6) and (7). For instance the even case follows by replacing \(x\) by \(x \sqrt{1+q}\) and letting \(q \rightarrow -1\) in (6).
We introduced a parity–sum statistic on permutations and studied its distribution on alternating permutations, leading to two families of \(q\)–polynomials \(F_n(q)\) and \(G_n(q)\) refining the Euler numbers. These correspond to the up–down and down–up cases. Parity–dependent reciprocity relations between these polynomials were established, together with self–reciprocity in odd lengths.
Split–at–\(1\) recursions were derived for the parity–sum \(q\)–Euler polynomials. At \(q=1\), these recursions reduce to André’s convolution identity for the Euler numbers.
The distribution of the parity–sum statistic over the full symmetric group was also determined, yielding closed formulas in terms of \(q\)–binomial coefficients.
The computed examples show that \(F_n(q)\) and \(G_n(q)\) fail to be unimodal even in the case of odd \(n\) (e.g., \(n=5\)), where symmetry holds. It is also possible that the coefficients of these polynomials admit an alternative combinatorial interpretation.