Connecting descent and peak polynomials

Abstract

A permutation $\sigma=\sigma_1 \sigma_2 \cdots \sigma_n$ has a descent at $i$ if $\sigma_i>\sigma_{i+1}$. A descent $i$ is called a peak if $i>1$ and $i-1$ is not a descent. The size of the set of all permutations of $n$ with a given descent set is a polynomials in $n$, called the descent polynomial. Similarly, the size of the set of all permutations of $n$ with a given peak set, adjusted by a power of $2$ gives a polynomial in $n$, called the peak polynomial. In this work we give a unitary expansion of descent polynomials in terms of peak polynomials. Then we use this expansion to give an interpretation of the coefficients of the peak polynomial in a binomial basis, thus giving a constructive proof of the peak polynomial positivity conjecture.

Keywords

• binomial coefficients
• descent
• peak
• permutations

Supporting Institution

University Of Southern California

Thanks

The author would like to thank Mohamed Omar for an inspiring seminar talk on the subject. The author is also immensely grateful to Alexander Diaz-Lopez and Erik Insko for spotting an error with the initial statement of the main result, and their many helpful suggestions and comments in the following discussion. This work was partially supported by the USC Graduate School Final Year Fellowship

References

1. [1] M. Aguiar, N. Bergeron and K. Nyman, The peak algebra and the descent algebras of types B and D, Trans. Amer. Math. Soc. 356, 2781-2824, 2004.
2. [2] S. Billey, K. Burdzy and B. Sagan, Permutations with given peak set, J. Integer Seq. 16(6), Article 13.6.1, 18 pages, 2013.
3. [3] A. Diaz-Lopez, P. Harris, E. Insko and M. Omar, A proof of the peak polynomial positivity conjecture, J. Combin. Theory Ser. A 149, 21-29, 2017.
4. [4] A. Diaz-Lopez, P. Harris, E. Insko, M. Omar and B. Sagan, Descent polynomials, Discrete Math. 342 (6), 1674-1686, 2019.
5. [5] P. MacMahon, Combinatory analysis, Vol. I, II (bound in one volume), Dover Publications, Inc., Mineola, NY 2004.