A New Class of Refined Eulerian Polynomials

Hua Sun College of Sciences Dalian Ocean University Dalian 116023 PR China

                      sunhua@dlou.edu.cn

Abstract In this note we introduce a new class of refined Eulerian polynomials defined by

A_{n}(p, q) = ∑_{π∈𝔖_{n}} p^{odes (π)}q^{edes (π)},

where odes (π) and edes (π) enumerate the number of descents of permutation π in odd and even positions, respectively. We show that the refined Eulerian polynomials A_{2k+1}(p, q), k = 0, 1, 2, …, and (1 + q)A_{2k}(p, q), k = 1, 2, …, have a nice symmetry property.

1 Introduction

Let f(q) = a_{r}q^{r} + ⋯ + a_{s}q^{s}(r ≤ s), with a_{r} ≠ 0 and a_{s} ≠ 0, be a real polynomial. The polynomial f(q) is palindromic if a_{r+i} = a_{s−i} for any i. Following Zeilberger [7], define the darga of f(q) to be r + s. The set of all palindromic polynomials of darga n is a vector space [6] with gamma basis

Γ_{n} := {q^{i}(1 + q)^{n−2i} | 0 ≤ i ≤ ⌊n/2⌋}.

Let f(p, q) be a nonzero bivariate polynomial. The polynomial f(p, q) is palindromic of darga n if it satisfies the following two equations:

f(p, q) = f(q, p),

f(p, q) = (pq)^{n}f(1/p, 1/q).

See Adin et al. [1] for details. It is known [4] that the set of all palindromic bivariate polynomials of darga n is a vector space with gamma basis

B_{n} := {(pq)^{i}(p + q)^{j}(1 + pq)^{n−2i−j} | i, j ≥ 0, 2i + j ≤ n}.

Let 𝔖_{n} denote the set of all permutations of the set [n] := {1, 2, …, n}. For a permutation π = π_{1}π_{2} ⋯ π_{n} ∈ 𝔖_{n}, an index i ∈ [n − 1] is a descent of π if π_{i} > π_{i+1}, and des (π) denotes the number of descents of π. The classic Eulerian polynomial is defined as the generating polynomial for the statistic des over the set 𝔖_{n}, i.e.,

A_{n}(q) = ∑_{π∈𝔖_{n}} q^{des (π)}.

Foata and Schützenberger [3] proved that the Eulerian polynomial A_{n}(q) can be expressed in terms of the gamma basis Γ_{n} with nonnegative integer coefficients. A polynomial with nonnegative coefficients under the gamma basis Γ_{n} is palindromic and unimodal [5].

Ehrenborg and Readdy [2] studied the number of ascents in odd position on 0, 1-words. We define similar statistics on permutations. For a permutation π ∈ 𝔖_{n}, an index i ∈ [n−1] is an odd descent of π if π_{i} > π_{i+1} and i is odd, an even descent of π if π_{i} > π_{i+1} and i is even, an odd ascent of π if π_{i} < π_{i+1} and i is odd, an even ascent of π if π_{i} < π_{i+1} and i is even. Let Odes (π), Edes (π), Oasc (π) and Easc (π) denote the set of all odd descents, even descents, odd ascents and even ascents of π, respectively. The corresponding cardinalities are odes (π), edes (π), oasc (π) and easc (π), respectively. Note that we can also define the above four statistics on words of length n. The joint distribution of odd and even descents on 𝔖_{n} is denoted by A_{n}(p, q), i.e.,

A_{n}(p, q) = ∑_{π∈𝔖_{n}} p^{odes (π)}q^{edes (π)}.

The polynomial A_{n}(p, q) is a bivariate polynomial of degree n − 1. The monomial with degree n − 1 is p^{⌊n/2⌋}q^{⌊(n−1)/2⌋} only. If p = q, then A_{n}(q, q) = A_{n}(q) is the classic Eulerian polynomial. Thus A_{n}(p, q), n = 1, 2, …, can be seen as a class of refined Eulerian polynomials. For example, we have

A_{1}(p, q) = 1,
A_{2}(p, q) = 1 + p,
A_{3}(p, q) = 1 + 2p + 2q + pq,
A_{4}(p, q) = 1 + 6p + 5q + 5p^{2} + 6pq + p^{2}q,
A_{5}(p, q) = 1 + 13p + 13q + 16p^{2} + 34pq + 16q^{2} + 13p^{2}q + 13pq^{2} + p^{2}q^{2},
A_{6}(p, q) = 1 + 29p + 28q + 89p^{2} + 152pq + 61q^{2} + 61p^{3} + 152p^{2}q
+ 89pq^{2} + 28p^{3}q + 29p^{2}q^{2} + p^{3}q^{2}.

For convenience, we denote

Ã_{n}(p, q) = \begin{cases}A_{n}(p, q), & if n = 2k + 1, \\ (1 + q)A_{n}(p, q), & if n = 2k. \end{cases}

Our main result is the following

Theorem 1. For any n = 1, 2, …, the polynomial Ã_{n}(p, q) is palindromic of darga ⌊\frac{n}{2}⌋.

In the next section we give a proof of Theorem 1. In Section 3 we study the case q = 1 and the case p = 1, the polynomials A_{n}(p, 1) and A_{n}(1, q) are the generating functions for the statistics odes and edes over the set 𝔖_{n}, respectively. In the last section, we propose a conjecture that Ã_{n}(p, q) can be expressed in terms of the gamma basis B⌊_{\frac{n}{2}}⌋ with nonnegative integer coefficients.

2 The proof of Theorem 1

Let π = π_{1}π_{2} ⋯ π_{n} ∈ 𝔖_{n}, we define the reversal π^{r} of π to be

π^{r} := π_{n}π_{n−1} ⋯ π_{1},

the complement π^{c} of π to be

π^{c} := (n + 1 − π_{1})(n + 1 − π_{2}) ⋯ (n + 1 − π_{n}),

and the reversal-complement π^{rc} of π to be

π^{rc} := (π^{c})^{r} = (π^{r})^{c}.

If i is a descent of π, then i is an ascent of π^{c} and if i is an ascent of π, then i is a descent of π^{c}. In other words, odes (π) + odes (π^{c}) = ⌊\frac{n}{2}⌋ and edes (π) + edes (π^{c}) = ⌊\frac{n−1}{2}⌋. Then

A_{n}(p, q) = ∑_{π∈𝔖_{n}} p^{odes (π)}q^{edes (π)} = ∑_{π∈𝔖_{n}} p^{⌊^{\frac{n}{2}}⌋−odes (π^{c})}q^{⌊^{\frac{n−1}{2}}⌋−edes (π^{c})}

= p^{⌊^{\frac{n}{2}}⌋}q^{⌊^{\frac{n−1}{2}}⌋} ∑_{π∈𝔖_{n}} (\frac{1}{p})^{odes (π^{c})} (\frac{1}{q})^{edes (π^{c})} = p^{⌊^{\frac{n}{2}}⌋}q^{⌊^{\frac{n−1}{2}}⌋}A_{n} (\frac{1}{p}, \frac{1}{q}) .

Specially, for any k = 1, 2, …, we have A_{2k}(p, q) = p^{k}q^{k−1}A_{2k}(1/p, 1/q) and for any k = 0, 1, 2, …, we have A_{2k+1}(p, q) = (pq)^{k}A_{2k+1}(1/p, 1/q).

It can be derived that i is a descent of π if and only if i is an ascent of π^{c}. It is also easy to see that i is a descent of π if and only if n − i is an ascent of π^{r}. Then, given a permutation π = π_{1}π_{2} ⋯ π_{2k+1} ∈ 𝔖_{2k+1},

i is a descent of π if and only if 2k + 1 − i is a descent of π^{rc}.

Specially, i is an odd descent of π if and only if 2k + 1 − i is an even descent of π^{rc}, and i is an even descent of π if and only if 2k + 1 − i is an odd descent of π^{rc}. So we have

Ã_{2k+1}(p, q) = ∑_{π∈𝔖_{2k+1}} p^{odes (π)}q^{edes (π)} = ∑_{π∈𝔖_{2k+1}} p^{edes (π^{rc})}q^{odes (π^{rc})} = Ã_{2k+1}(q, p).

Thus for any k = 1, 2, …, the polynomial Ã_{2k+1}(p, q) is palindromic of darga k. In addition,

Ã_{2k}(p, q) = (1 + q)p^{k}q^{k−1}A_{2k} (\frac{1}{p}, \frac{1}{q}) = (1 + \frac{1}{q}) p^{k}q^{k}A_{2k} (\frac{1}{p}, \frac{1}{q}) = (pq)^{k}Ã_{2k+1} (\frac{1}{p}, \frac{1}{q}) .

The last part is to prove that Ã_{2k}(p, q) = Ã_{2k}(q, p), that is,

∑_{π∈𝔖_{2k}} p^{odes (π)}[q^{edes (π)} + q^{edes (π)+1}] = ∑_{π∈𝔖_{2k}} q^{odes (π)}[p^{edes (π)} + p^{edes (π)+1}].

Let 𝔖′_{2k} = {π(2k + 1), π0 | π ∈ 𝔖_{2k}}, 𝔖′′_{2k} = {(2k + 1)π, 0π | π ∈ 𝔖_{2k}}, and let π = π_{1}π_{2} ⋯ π_{2k} ∈ 𝔖_{2k}. Define a map ψ : 𝔖′_{2k} → 𝔖′′_{2k} by

ψ(πx) = \begin{cases}(2k + 1)(2k + 1 − π_{2k})(2k + 1 − π_{2k−1}) ⋯ (2k + 1 − π_{1}), & if x = 0, \\ 0(2k + 1 − π_{2k})(2k + 1 − π_{2k−1}) ⋯ (2k + 1 − π_{1}), & if x = 2k + 1. \end{cases}

Given a permutation π ∈ 𝔖_{2k}, it is no hard to see that

odes (π(2k + 1)) = odes (π),  edes (π(2k + 1)) = edes (π),
odes (π0) = odes (π),  edes (π0) = edes (π) + 1,
odes ((2k + 1)π) = edes (π) + 1,  edes ((2k + 1)π) = odes (π),
odes (0π) = edes (π),  edes (0π) = odes (π).

Thus

odes (ψ(π(2k + 1))) = odes (0π^{rc}) = edes (π^{rc}),
edes (ψ(π(2k + 1))) = edes (0π^{rc}) = odes (π^{rc}),
odes (ψ(π0)) = odes ((2k + 1)π^{rc}) = edes (π^{rc}) + 1,
edes (ψ(π0)) = edes ((2k + 1)π^{rc}) = odes (π^{rc}).

Obviously, the map ψ is an involution. Then

∑_{π∈𝔖_{2k}} p^{odes (π)}[q^{edes (π)} + q^{edes (π)+1}]

= ∑_{π∈𝔖_{2k}} p^{odes (π(2k+1))}q^{edes (π(2k+1))} + ∑_{π∈𝔖_{2k}} p^{odes (π0)}q^{edes (π0)}

= ∑_{π∈𝔖_{2k}} p^{odes (ψ(π(2k+1)))}q^{edes (ψ(π(2k+1)))} + ∑_{π∈𝔖_{2k}} p^{odes (ψ(π0))}q^{edes (ψ(π0))}

= ∑_{π∈𝔖_{2k}} p^{edes (π^{rc})}q^{odes (π^{rc})} + ∑_{π∈𝔖_{2k}} p^{edes (π^{rc})+1}q^{odes (π^{rc})}

= ∑_{π∈𝔖_{2k}} q^{odes (π)}[p^{edes (π)} + p^{edes (π)+1}].

Thus for any k = 1, 2, …, the polynomial Ã_{2k}(p, q) is palindromic of darga k. This completes the proof.

3 The case p = 1 and the case q = 1

If q = 1, the polynomial A_{n}(p, 1) is the generating function for the statistic odes over the set 𝔖_{n}, and if p = 1, the polynomial A_{n}(1, q) is the generating function for the statistic edes over the set 𝔖_{n}. More precisely, we have

Proposition 2. Let n be a positive integer. Then

∑_{π∈𝔖_{n}} p^{odes (π)} = A_{n}(p, 1) = \frac{n!}{2^{⌊^{\frac{n}{2}}⌋}} (1 + p)^{⌊^{\frac{n}{2}}⌋},  (1)

and

∑_{π∈𝔖_{n}} q^{edes (π)} = A_{n}(1, q) = \frac{n!}{2^{⌊^{\frac{n−1}{2}}⌋}} (1 + q)^{⌊^{\frac{n−1}{2}}⌋}.  (2)

Proof. It is easy to verify that the equalities 1 and 1 are true for n = 1 and n = 2. Let n ≥ 3 and let π = π_{1}π_{2} ⋯ π_{n} ∈ 𝔖_{n}. For any i = 1, 2, …, ⌊n/2⌋, define a map φ_{i} : 𝔖_{n} → 𝔖_{n} by

φ_{i}(π) = π_{1}π_{2} ⋯ π_{2i}π_{2i−1} ⋯ π_{n},

i.e., φ_{i}(π) is obtained by swapping π_{2i} with π_{2i−1} in π. Obviously, the map φ_{i} is an involution, i = 1, 2, …, ⌊n/2⌋, and φ_{i} and φ_{j} commute for all i, j ∈ {1, 2, …, ⌊n/2⌋}. For any subset S ⊆ {1, 2, …, ⌊n/2⌋}, we define a map φ_{S} : 𝔖_{n} → 𝔖_{n} by

φ_{S}(π) = ∏_{i∈S} φ_{i}(π).

The group ℤ_{2}^{⌊n/2⌋} acts on 𝔖_{n} via the maps φ_{S}, S ⊆ {1, 2, …, ⌊n/2⌋}. For any π ∈ 𝔖_{n}, let Orb^{∗}(π) denote the orbit including π under the group action. There is a unique permutation in Orb^{∗}(π), denoted by π̂, such that

π̂_{1} < π̂_{2}, π̂_{3} < π̂_{4}, …, π̂_{2⌊n/2⌋−1} < π̂_{2⌊n/2⌋}.

It is not hard to prove that odes (π̂) = 0 and odes (φ_{S}(π̂)) = |S| for any S ⊆ {1, 2, …, ⌊n/2⌋}. Then

∑_{σ∈Orb^{∗}(π)} p^{odes (σ)} = (1 + p)^{⌊^{\frac{n}{2}}⌋}.

Let 𝔖_{n}^{∗} consist of all the permutations in 𝔖_{n} such that

π_{1} < π_{2}, π_{3} < π_{4}, …, π_{2⌊n/2⌋−1} < π_{2⌊n/2⌋}.

The cardinality of the set 𝔖_{n}^{∗} is

\binom{n}{2}\binom{n − 2}{2} ⋯ \binom{n + 2 − 2 ⌊\frac{n}{2}⌋}{2} = \frac{n!}{2^{⌊^{\frac{n}{2}}⌋}} .

Then

∑_{π∈𝔖_{n}} p^{odes (π)} = A_{n}(p, 1) = \frac{n!}{2^{⌊^{\frac{n}{2}}⌋}} (1 + p)^{⌊^{\frac{n}{2}}⌋}.

Similarly, for any i = 1, 2, …, ⌊(n − 1)/2⌋, we define a map ϕ_{i} : 𝔖_{n} → 𝔖_{n} by

ϕ_{i}(π) = π_{1} ⋯ π_{2i+1}π_{2i} ⋯ π_{n},

i.e., ϕ_{i}(π) is obtained by swapping π_{2i} with π_{2i+1} in π. Obviously, the map ϕ_{i} is an involution, i = 1, 2, …, ⌊(n − 1)/2⌋, and ϕ_{i} and ϕ_{j} commute for all i, j ∈ {1, 2, …, ⌊(n − 1)/2⌋}. For any subset S ⊆ {1, 2, …, ⌊(n − 1)/2⌋}, we define a map ϕ_{S} : 𝔖_{n} → 𝔖_{n} by

ϕ_{S}(π) = ∏_{i∈S} ϕ_{i}(π).

The group ℤ_{2}^{⌊(n−1)/2⌋} acts on 𝔖_{n} via the maps ϕ_{S}, S ∈ [⌊(n − 1)/2⌋]. For any π ∈ 𝔖_{n}, let Orb^{∗∗}(π) denote the orbit including π under the group action. There is a unique permutation in Orb^{∗∗}(π), denoted by π̄, such that

π̄_{2} < π̄_{3}, π̄_{4} < π̄_{5}, …, π̄_{2⌊(n−1)/2⌋} < π̄_{2⌊(n−1)/2⌋+1}.

It is easily obtained that edes (π̄) = 0 and edes (ϕ_{S}(π̄)) = |S| for any S ⊆ {1, 2, …, ⌊(n − 1)/2⌋}. Then

∑_{σ∈Orb^{∗∗}(π)} q^{edes (σ)} = (1 + q)^{⌊^{\frac{n−1}{2}}⌋}.

Let 𝔖_{n}^{∗∗} consist of all the permutations in 𝔖_{n} such that

π_{2} < π_{3}, π_{4} < π_{5}, …, π_{2⌊(n−1)/2⌋} < π_{2⌊(n−1)/2⌋+1}.

The cardinality of the set 𝔖_{n}^{∗∗} is

\binom{n}{2}\binom{n−2}{2} ⋯ \binom{n+2−2⌊\frac{n−1}{2}⌋}{2} = _{\frac{n!}{2^{⌊^{\frac{n−1}{2}}⌋}}} , if n is odd,
2\binom{n}{2}\binom{n−2}{2} ⋯ \binom{n+2−2⌊\frac{n−1}{2}⌋}{2} = _{\frac{n!}{2^{⌊^{\frac{n−1}{2}}⌋}}} , if n is even.

Then

∑_{π∈𝔖_{n}} q^{edes (π)} = A_{n}(1, q) = \frac{n!}{2^{⌊^{\frac{n−1}{2}}⌋}} (1 + q)^{⌊^{\frac{n−1}{2}}⌋}.

4 Remarks

The set of palindromic bivariate polynomials of darga k is a vector space with gamma basis

B_{k} = {(pq)^{i}(p + q)^{j}(1 + pq)^{k−2i−j} | i, j ≥ 0, 2i + j ≤ k}.

Thus the refined Eulerian polynomials Ã_{n}(p, q), n = 1, 2, …, can be expanded in terms of the gamma basis B⌊_{\frac{n}{2}}⌋. For example,

Ã_{1}(p, q) = A_{1}(p, q) = 1,
Ã_{2}(p, q) = (1 + q)A_{2}(p, q) = (1 + q)(1 + p) = 1 + p + q + pq

= (1 + pq) + (p + q),

Ã_{3}(p, q) = A_{3}(p, q) = 1 + 2p + 2q + pq = (1 + pq) + 2(p + q),
Ã_{4}(p, q) = (1 + q)A_{4}(p, q) = (1 + q)(1 + 6p + 5q + 5p^{2} + 6pq + p^{2}q)

= 1 + 6p + 6q + 5p^{2} + 12pq + 5q^{2} + 6p^{2}q + 6pq^{2} + p^{2}q^{2} = (1 + pq)^{2} + 6(p + q)(1 + pq) + 5(p + q)^{2},

Ã_{5}(p, q) = A_{5}(p, q) = 1 + 13p + 13q + 16p^{2} + 34pq + 16q^{2} + 13p^{2}q + 13pq^{2} + p^{2}q^{2}

= (1 + pq)^{2} + 13(p + q)(1 + pq) + 16(p + q)^{2},

Ã_{6}(p, q) = (1 + q)A_{6}(p, q)

= (1 + q)(1 + 29p + 28q + 89p^{2} + 152pq + 61q^{2}

+ 61p^{3} + 152p^{2}q + 89pq^{2} + 28p^{3}q + 29p^{2}q^{2} + p^{3}q^{2}) = 1 + 29p + 29q + 89p^{2} + 89q^{2} + 181pq + 61p^{3} + 241p^{2}q

+ 241pq^{2} + 61q^{3} + 181p^{2}q^{2} + 89p^{3}q + 89pq^{3} + 29p^{3}q^{2} + 29p^{2}q^{3} + p^{3}q^{3} = (1 + pq)^{3} + 29(p + q)(1 + pq)^{2} + 89(p + q)^{2}(1 + pq) + 61(p + q)^{3}.

We conjecture that for any n ≥ 1, all c_{j} are positive integers in the following expansion

Ã_{n}(p, q) = \begin{matrix}⌊ & \frac{n}{2} & ⌋ \\ ∑ \\ j=0 \end{matrix} c_{j}(p + q)^{j}(1 + pq)^{⌊^{\frac{n}{2}}⌋−j}.

5 Acknowledgments

I am grateful to my advisor Prof. Yi Wang for his valuable comments and suggestions. I also would like to thank the referee for his/her careful reading and many helpful suggestions.

This work was partially supported by the National Natural Science Foundation of China (Grant No. 11526044) and the Doctoral Scientific Research Starting Foundation of Liaoning Province (No. 20170520451).

References

[1] R. M. Adin, E. Bagno, E. Eisenberg, S. Reches, and M. Sigron, Towards a combinatorial proof of Gessel’s conjecture on two-sided gamma positivity: a reduction to simple permutations, preprint, 2017. Available at http://arxiv.org/abs/1711.06511.

[2] R. Ehrenborg and M. A. Readdy, The Gaussian coefficient revisited, J. Integer Sequences, 19 (2016), Article 16.7.8.

[3] D. Foata and M.-P. Schützenberger, Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, Vol. 138, Springer-Verlag, 1970.

[4] Z. Lin, Proof of Gessel’s γ-positivity conjecture, Electron. J. Combin., 23 (3) (2016), paper P3.15.

[5] T. K. Petersen, Eulerian Numbers, Birkhauser, 2015.

[6] H. Sun, Y. Wang, and H. X. Zhang, Polynomials with palindromic and unimodal coefficients, Acta Mathematica Sinica, English Series, 31 (4) (2015), 565–575.

[7] D. Zeilberger, A one-line high school proof of the unimodality of the Gaussian polynomials \binom{n}{k}_{q} for k < 20, in D. Stanton, ed., q-Series and Partitions, IMA Volumes in Mathematics and Its Applications, Vol. 18, Springer, 1989, pp. 67–72.

2010 Mathematics Subject Classification: Primary 05A05; Secondary 05A15, 05A19. Keywords: odd descent, even descent, Eulerian polynomial, γ-positivity.

Received January 31 2018; revised versions received May 13 2018; May 17 2018. Published in Journal of Integer Sequences, May 26 2018.

Return to Journal of Integer Sequences home page.