Counting permutations by alternating descents (Q470946): Difference between revisions

Summary: 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 \textit{L. Nicolaescu} [``Combinatorial Morse functions and random permutations'', \url{http://mathoverflow.net/questions/86193}]. The generating function can be expressed~as the reciprocal of a sum involving Euler numbers: \[ \bigg(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\bigg)^{-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(\frac{1}{2}x)+3\cosh(\frac{1}{2}\sqrt{3}x)}{3\cos(\frac{1}{2}x)-\sqrt{3}\sinh(\frac{1}{2}\sqrt{3}x)}, \] which we then show is equal to \((\ast)\). The second proof derives \((*)\) directly from general permutation enumeration techniques, using noncommutative symmetric functions. The generating function \((\ast)\) is an ``alternating'' analogue of David and Barton's generating function \[ \bigg(1-x+\frac{x^{3}}{3!}-\frac{x^{4}}{4!}+\frac{x^{6}}{6!}-\frac{x^{7}}{7!}+\cdots\bigg)^{-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 \textit{D. Chebikin} [Electron. J. Comb. 15, No. 1, Research Paper R132, 34 p. (2008; Zbl 1179.05004)] and \textit{J. B. Remmel} [Ann. Comb. 16, No. 3, 625--650 (2012; Zbl 1256.05009)].