Counting Permutations by Alternating Descents
Ira M. Gessel
Yan Zhuang
Keywords: permutations, peaks, valleys, descents, noncommutative symmetric functions
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
\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)},
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.