Counting permutations by alternating descents

Ira M. Gessel¹ ; Yan Zhuang¹

¹Brandeis University

The electronic journal of combinatorics, Tome 21 (2014) no. 4

Résumé

We find the exponential generating function for permutations with all valleys even and all peaks odd, and use it to determine the asymptotics for its coefficients, answering a question posed by Liviu Nicolaescu. The generating function can be expressed as the reciprocal of a sum involving Euler numbers: \[\left(1-E_1x+E_{3}\frac{x^{3}}{3!}-E_{4}\frac{x^{4}}{4!}+E_{6}\frac{x^{6}}{6!}-E_{7}\frac{x^{7}}{7!}+\cdots\right)^{-1},\tag{$*$}\]where $\sum_{n=0}^\infty E_n x^n\!/n! = \sec x + \tan x$. We give two proofs of this formula. The first uses a system of differential equations whose solution gives the generating function\begin{equation*}\frac{3\sin\left(\frac{1}{2}x\right)+3\cosh\left(\frac{1}{2}\sqrt{3}x\right)}{3\cos\left(\frac{1}{2}x\right)-\sqrt{3}\sinh\left(\frac{1}{2}\sqrt{3}x\right)},\end{equation*} which we then show is equal to $(*)$. The second proof derives $(*)$ directly from general permutation enumeration techniques, using noncommutative symmetric functions. The generating function $(*)$ is an "alternating" analogue of David and Barton's generating function \[\left(1-x+\frac{x^{3}}{3!}-\frac{x^{4}}{4!}+\frac{x^{6}}{6!}-\frac{x^{7}}{7!}+\cdots\right)^{-1},\]for permutations with no increasing runs of length 3 or more. Our general results give further alternating analogues of permutation enumeration formulas, including results of Chebikin and Remmel.

Détail

DOI : 10.37236/4624

Classification : 05A15, 05A05, 05E05
Mots-clés : permutations, peaks, valleys, descents, noncommutative symmetric functions