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
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] 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] 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] 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] A. Diaz-Lopez, P. Harris, E. Insko, M. Omar and B. Sagan, Descent polynomials, Discrete Math. 342 (6), 1674-1686, 2019.
- [5] P. MacMahon, Combinatory analysis, Vol. I, II (bound in one volume), Dover Publications, Inc., Mineola, NY 2004.
Abstract
References
- [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] 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] 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] A. Diaz-Lopez, P. Harris, E. Insko, M. Omar and B. Sagan, Descent polynomials, Discrete Math. 342 (6), 1674-1686, 2019.
- [5] P. MacMahon, Combinatory analysis, Vol. I, II (bound in one volume), Dover Publications, Inc., Mineola, NY 2004.
Details
| Primary Language | English |
|---|---|
| Subjects | Mathematical Sciences |
| Journal Section | Mathematics |
| Authors | |
| Early Pub Date | August 15, 2023 |
| Publication Date | April 23, 2024 |
| Published in Issue | Year 2024 Volume: 53 Issue: 2 |