\documentclass[12pt]{article} \usepackage{e-jc} \usepackage[T1]{fontenc} \usepackage{amsthm,amsmath,amssymb} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \usepackage{mathtools} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \theoremstyle{plain} \newtheorem{thm}{Theorem} \newtheorem{lem}[thm]{Lemma} \newtheorem{cor}[thm]{Corollary} \usepackage{titlesec} \titleformat{\section} {\normalfont\large\bfseries}{\thesection.}{.8ex}{} \titleformat{\subsection} {\normalfont\bfseries}{\thesubsection.}{.8ex}{} \renewcommand{\S}{\mathfrak S} \newcommand{\binomE}[2]{\binom{#1}{#2}_E} \newcommand{\up}{\kern -2.7pt\uparrow} \newcommand{\h}{\mathbf h} \renewcommand{\r}{\mathbf r} \newcommand{\Sym}{\mathbf{Sym}} \renewcommand{\Bar}{\,|\,} \DeclareMathOperator{\des}{des} \DeclareMathOperator{\altdes}{altdes} \DeclareMathOperator{\maj}{maj} \DeclareMathOperator{\altmaj}{altmaj} \newcommand{\leftprod}[1]{\overset{\longleftarrow}{\prod_{#1}}} \title{Counting permutations by alternating descents} \author{Ira M. Gessel\qquad Yan Zhuang\\ \small Department of Mathematics\\[-0.8ex] \small Brandeis University\\[-0.8ex] \small \tt \{gessel,zhuangy\}@brandeis.edu } \date{\dateline{Aug 23, 2014}{Oct 7, 2014}\\ \small Mathematics Subject Classifications: 05A15, 05A05, 05E05} \begin{document} \maketitle \begin{abstract} 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. \bigskip\noindent \textbf{Keywords:} permutation enumeration; alternating descents; Euler numbers; noncommutative symmetric functions \end{abstract} \section{Introduction} This paper was inspired by a question posed by Liviu Nicolaescu on discrete Morse functions arising in combinatorial topology \cite{Nicolaescu2012}, which reduces to the following combinatorial problem. Let $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$ be a permutation in $\mathfrak{S}_{n}$, the set of permutations of $[n]=\{1,2,\dots,n\}$ (or more generally, any sequence of distinct integers). We say that $i$ is a \emph{peak} of $\pi$ if $\pi_{i-1}<\pi_{i}>\pi_{i+1}$ and that $j$ is a \emph{valley} of $\pi$ if $\pi_{j-1}>\pi_{j}<\pi_{j+1}$. For example, if $\pi=4762315$, then its peaks are 2 and 5, and its valleys are 4 and 6. Let $f(n)$ be the number of permutations in $\mathfrak{S}_{n}$ that have all valleys even and all peaks odd. What is the behavior of $f(n)/n!$ as $n\rightarrow\infty$? To answer this question, we find the exponential generating function for permutations with all valleys even and all peaks odd and use it to derive an asymptotic formula for $f(n)/n!$, thus answering Nicolaescu's question. In Section \ref{s-2}, we show that the exponential generating function $F(x)$ for $f(n)$ is given by the formula \begin{equation} \label{e-F1} F(x) =\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} by a finding recurrences for $f$ and for an auxiliary sequence, and solving the corresponding system of differential equations. It follows from this generating function that $f(n)/n!$ is asymptotic to $2\beta^{n+1}$, where $\beta = 0.7693323708\cdots$ is the zero of the denominator of $F(x)$ of smallest modulus. In Section \ref{s-3}, we show that \begin{equation} \label{e-F2} F(x) = \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}, \end{equation} where the Euler numbers $E_n$ are defined by $\sum_{n=0}^\infty E_n x^n\!/n! = \sec x + \tan x$. Although we can prove directly that \eqref{e-F1} and \eqref{e-F2} are equivalent, we also give a more conceptual direct proof of \eqref{e-F2}. First we recall a result of David and Barton \cite[pp.~156--157]{David1962}: the exponential generating function for permutations that avoid the increasing consecutive pattern $12\cdots m$ (i.e., permutations in which every increasing run has length less than $m$) is \begin{align*} \left(1-x+\frac{x^{m}}{m!}-\frac{x^{m+1}}{\left(m+1\right)!}+\frac{x^{2m}}{\left(2m\right)!}-\frac{x^{2m+1}}{\left(2m+1\right)!}+\cdots\right)^{-1}, \end{align*} which for $m=3$ is \begin{equation} \label{e-m=3} \left(1-x+\frac{x^{3}}{3!}-\frac{x^{4}}{4!}+\frac{x^{6}}{6!}-\frac{x^{7}}{7!}+\cdots\right)^{-1}. \end{equation} We can explain the similarity between \eqref{e-F2} and \eqref{e-m=3} by using the concept of ``alternating descents'' introduced by Denis Chebikin \cite{chebikin}. We say that $i\in [n-1]$ is a \emph{descent} of a permutation $\pi$ in $\S_n$ if $\pi_i>\pi_{i+1}$. An \emph{increasing run} of $\pi$ is a maximal consecutive subsequence of $\pi$ containing no descents. So the increasing runs of $253146$ are $25$, $3$, and $146$. Note that the number of increasing runs of a nonempty permutation is one more than the number of descents. Following Stanley \cite{st-alt}, we say that $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$ is an \emph{alternating }permutation if $\pi_{1}>\pi_{2}<\pi_{3}>\pi_{4}<\cdots$. If instead $\pi_{1}<\pi_{2}>\pi_{3}<\pi_{4}>\cdots$, then we say that $\pi$ is \emph{reverse-alternating}. It is well known that the number of alternating permutations of $[n]$ is $E_n$. Alternating permutations of length $n$ are in bijection with reverse-alternating permutations of length $n$ via complementation; that is, if $\pi=\pi_{1}\pi_{2}\cdots\pi_{n}$ is alternating, then its complement \[ \pi^{c}=\left(n+1-\pi_{1}\right)\left(n+1-\pi_{2}\right)\cdots\left(n+1-\pi_{n}\right) \] is reverse-alternating, and vice versa. Thus, the Euler numbers count reverse-alternating permutations as well. Following Chebikin, we say that $i\in [n-1]$ is an \emph{alternating descent} of $\pi$ if $i$ is odd and $\pi_i>\pi_{i+1}$ or if $i$ is even and $\pi_i<\pi_{i+1}$. We define an \emph{alternating run}% \footnote{The term ``alternating run'' has been used for a different concept (see Definition 1.37 in \cite{Bona2012}, or \cite{oeisA059427}), but our usage here should cause no confusion.} of $\pi$ to be a maximal consecutive subsequence of $\pi$ containing no alternating descents. Thus the alternating runs of the permutation $3421675$ are $342$, $1$, and $675$. An alternating run that starts in an odd position will be a reverse-alternating permutation and an alternating run that starts in an even position will be an alternating permutation. The number of alternating runs of a permutation will be one more than the number of alternating descents. A peak in an even position of a permutation $\pi$ will correspond to a subsequence $\pi_{2i-1}<\pi_{2i}>\pi_{2i+1}$ and thus will be contained in an alternating run of length at least~3, and similarly a valley in an odd position must also be contained in an alternating run of length at least 3. Conversely, any alternating run of length at least 3 contains (as its second entry) either a peak in an even position or a valley in an odd position. Thus the permutations with all valleys even and all peaks odd are the same as the permutations in which every alternating run has length less than 3. Then the similarity between \eqref{e-F2} and \eqref{e-m=3} can be explained by a general principle that whenever we have a formula like \eqref{e-m=3} that counts permutations with a restriction on increasing run lengths, there is an analogous formula, with $x^n\!/n!$ replaced by $E_n x^n\!/n!$, for counting permutations with the same restriction on alternating run lengths. We will make this idea precise in Section 3, using basic facts about noncommutative symmetric functions \cite{ncsf1}. In particular, we obtain Chebikin's formula \cite{chebikin} on ``alternating Eulerian polynomials'' that count permutations by the number of alternating descents, and Remmel's formula \cite{remmel} on counting permutations by the number of alternating descents and ``alternating major index.'' \section{Permutations with All Valleys Even and All Peaks Odd} \label{s-2} \subsection{The exponential generating function} In this section, we use recurrrences to derive the exponential generating function for permutations with all valleys even and all peaks odd. \begin{thm} \label{t-m=00003D3}Let $F$ be the exponential generating function for permutations with all valleys even and all peaks odd. Then $F$ is given by \begin{equation} \label{e-Fgf} F(x) =\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} The first few values of the coefficients $f(n)$ of $F(x)$ are as follows: \[\vbox{\halign{\ \hfil\strut$#$\hfil\ \vrule&&\hfil\ $#$\ \hfil\cr n&0&1&2&3&4&5&6&7&8&9&10&11&12\cr \noalign{\hrule} f(n)&1&1&2&4&13&50&229&1238&7614&52706&405581&3432022&31684445\cr}} \] \end{thm} To prove Theorem \ref{t-m=00003D3}, we first obtain recurrence relations for the coefficients of $F(x)$. \begin{lem} Let $f(n)$ be the number of permutations in $\S_n$ with all valleys even and all peaks odd, and let $g(n)$ be the number of such permutations that end with an ascent. Then \begin{equation} f(n+1)=\sum_{k=0}^{\left\lfloor \frac{n-1}{2}\right\rfloor }\binom{n}{2k}f(2k)f(n-2k)+\begin{cases} f(n), & \text{if $n$ is even,}\\ g(n), & \text{if $n$ is odd,} \end{cases}\label{e-recf} \end{equation} and \begin{equation} g(n+1)=\sum_{k=0}^{\left\lfloor \frac{n-2}{2}\right\rfloor }\binom{n}{2k}f(2k)\left[f(n-2k)-g(n-2k)\right] +\begin{cases} f(n), & \text{if $n$ is even,}\\ g(n), & \text{if $n$ is odd,} \end{cases}\label{e-recg} \end{equation} with $f(0)=g(0)=1$.\end{lem} \begin{proof} The initial conditions are true by convention. Let $\pi=\pi_{1}\pi_{2}\cdots\pi_{n+1}$ be an $\left(n+1\right)$-permutation with all peaks odd and all valleys even. We remove the largest letter $n+1$ to obtain two words with distinct letters, the subword $\pi^{\prime}$ of $\pi$ of all letters before $n+1$ and the subword $\pi^{\prime\prime}$ of $\pi$ of all letters after $n+1$. Apply the standard reduction map to $\pi^{\prime}$ and $\pi^{\prime\prime}$, replacing the $i$th smallest letter in each word by $i$, so that both words become permutations with the order relations among the letters in each word preserved. By a slight abuse of notation, call these permutations $\pi^{\prime}$ and $\pi^{\prime\prime}$. Let us consider three cases: \begin{itemize} \item If $\pi_{1}=n+1$, then $\pi^{\prime}$ is empty and $\pi^{\prime\prime}$ is an $n$-permutation with all peaks even and all valleys odd, but such $n$-permutations are in bijection (by complementation) with $n$-permutations with all peaks odd and all valleys even. Hence, there are $f(n)$ possibilities for $\pi^{\prime\prime}$ and thus for $\pi$, which corresponds to the case $k=0$ in (\ref{e-recf}). \item Now, suppose that $\pi_{i}=n+1$, where $10$, there exists $N$ such that for all $n>N$, we have \[ \left|f(n)\right|<\left(\frac{1}{\left|R\right|}+\epsilon\right)^{n}. \] Furthermore, for infinitely many $n$ we have \[ \left|f(n)\right|>\left(\frac{1}{\left|R\right|}-\epsilon\right)^{n}. \] \end{thm} The exponential growth formula implies that the growth rate of the coefficients of a meromorphic function can be determined from the location of its poles closest to the origin. We use this idea to extract the asympotic data from our exponential generating function $F$. \begin{thm} \label{t-asm}Let $f(n)$ be the number of $n$-permutations with all valleys even and all peaks odd. Then \[ \frac{f(n)}{n!}=2\beta^{n+1}+O\left(\delta^n \right), \mbox{ as }n\rightarrow\infty, \] where $\beta=0.7693323708\cdots$ and $\delta=0.3049639861\cdots$.\end{thm} \begin{proof} Let $F(z)$ be defined by \eqref{e-Fgf} as a function of a complex variable $z$. Let $D(z) ={3\cos(\frac{1}{2}z)-\sqrt{3}\sinh(\frac{1}{2}\sqrt{3}z)}$ be the denominator of $F(z)$. Then $D(z)$ is an entire function, so $F(z)$ is meromorphic on the entire complex plane. Using Maple, we find that the zero of $D(z)$ of smallest modulus is a simple zero at $z=\alpha:=1.299828316\cdots$ and the zeros with the second smallest modulus are at $z=-2.058295121\cdots\pm(2.552598427\cdots)i$ with modulus $\gamma:=3.279075713\cdots$. Then we can write \[ F(z)=\frac{J(z)}{z-\alpha}, \] where $J(z)$ is analytic in $|z|<\gamma$. Then \[ \frac{f(n)}{n!}=\left[z^{n}\right]\frac{J(\alpha)}{z-\alpha}+\left[z^{n}\right]\left(F(z)-\frac{J(\alpha)}{z-\alpha}\right) \] and \[ K(z):=F\left(z\right)-\frac{J(\alpha)}{z-\alpha} \] is analytic at $z=\alpha$, where $J(\alpha)/(z-\alpha)$ is the principal part of the Laurent expansion of $F(z)$ about $\alpha$. The singularities of $K$ closest to the origin have modulus $\gamma$, so by the exponential growth formula, we obtain \[ \left[z^{n}\right]\left(F(z)-\frac{J(\alpha)}{z-\alpha}\right)=O\left(\left(\gamma^{-1}+\epsilon\right)^{n}\right) \] as $n\rightarrow\infty$ for any $\epsilon>0$. But since the two singularities of $K(z)$ of smallest modulus are simple poles, we can replace $\gamma^{-1}+\epsilon$ with $\gamma^{-1}$. Thus \begin{align} \frac{f(n)}{n!} & =\left[z^{n}\right]\frac{J(\alpha)}{z-\alpha}+O\left(\gamma^{-n}\right)\nonumber \\ & =\left[z^{n}\right]\left(-\frac{J(\alpha)/\alpha}{1-\frac{z}{\alpha}}\right)+O\left(\gamma^{-n}\right)\nonumber \\ & =\left[z^{n}\right]\sum_{n=0}^{\infty}\left(-\frac{J(\alpha)}{\alpha^{n+1}}\right)z^{n}+O\left(\gamma^{-n}\right)\nonumber \\ & =-\frac{J(\alpha)}{\alpha^{n+1}}+O\left(\gamma^{-n}\right)\label{e-asm1} \end{align} as $n\rightarrow\infty$. It remains to determine $J(\alpha)$. Let $U(z)=1/F(z)$. We have that \[ J(z)=(z-\alpha)F(z), \] so \begin{align} J(\alpha) & =\lim_{z\rightarrow\alpha}(z-\alpha)F(z)\nonumber \\ & =\lim_{z\rightarrow\alpha}\frac{z-\alpha}{U(z)}\nonumber \\ & =\frac{1}{U^{\prime}(\alpha)}\label{e-asm2} \end{align} by L'H\^opital's rule. Moreover, \[ U^{\prime}(z)=-\frac{3}{2}\cdot\frac{\left[3\cos\left(\frac{1}{2}z\right)-\sqrt{3}\sinh\left(\frac{1}{2}\sqrt{3}z\right)\right]\left[\cos\left(\frac{1}{2}z\right)+\sqrt{3}\sinh\left(\frac{1}{2}\sqrt{3}z\right)\right]}{\left[3\sin\left(\frac{1}{2}z\right)+3\cosh\left(\frac{1}{2}\sqrt{3}z\right)\right]^{2}}-\frac{1}{2}, \] and since $3\cos\left(\frac{1}{2}\alpha\right)-\sqrt{3}\sinh\left(\frac{1}{2}\sqrt{3}\alpha\right)=0$, it follows that \[ U^{\prime}(\alpha)=-\frac{1}{2}. \] Therefore, from (\ref{e-asm1}) and (\ref{e-asm2}) we obtain \[ \frac{f(n)}{n!}=\frac{2}{\alpha^{n+1}}+O\left(\gamma^{-n}\right), \] and applying the substitutions $\beta:=\alpha^{-1}$ and $\delta:=\gamma^{-1}$ completes the result. \end{proof} By including more poles of $F(z)$, we could get better approximations. \section{Alternating Descents and Runs} \label{s-3} \subsection{The Euler number formula} Next we show that $F(x)$, as given in \eqref{e-Fgf}, is equal to \begin{multline*} \qquad\left(1-x+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} =\\ \left[\sum_{n=0}^{\infty}\left(E_{3n}\frac{x^{3n}}{\left(3n\right)!}-E_{3n+1}\frac{x^{3n+1}}{\left(3n+1\right)!}\right)\right]^{-1},\qquad \end{multline*} where the Euler numbers $E_n$ are defined by $\sum_{n=0}^\infty E_n x^n\!/n! = \sec x +\tan x$. Let $E(x)=\sec x+\tan x$. Then by multisection, we have \[ \sum_{n=0}^{\infty}E_{3n}\frac{x^{3n}}{\left(3n\right)!}=\frac{1}{3}\left(E(x)+E(\omega x)+E(\omega^{2}x)\right) \] and \[ \sum_{n=0}^{\infty}E_{3n+1}\frac{x^{3n+1}}{\left(3n+1\right)!}=\frac{1}{3}\left(E(x)+\omega^{-1}E(\omega x)+\omega^{-2}E(\omega^{2}x)\right), \] where $\omega$ is the primitive cube root of unity $e^{2\pi i/3}$. It can then be verified, for example by using Maple, that \begin{align} F(x) & =\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)}\nonumber \\ & =\left[\frac{1}{3}\left(E(x)+E(\omega x)+E(\omega^{2}x)\right)-\frac{1}{3}\left(E(x)+\omega^{-1}E(\omega x)+\omega^{-2}E(\omega^{2}x)\right)\right]^{-1}\nonumber \\ & =\left[\sum_{n=0}^{\infty}\left(E_{3n}\frac{x^{3n}}{\left(3n\right)!}-E_{3n+1}\frac{x^{3n+1}}{\left(3n+1\right)!}\right)\right]^{-1}.\label{e-FE} \end{align} Thus we see that \eqref{e-FE} is the exponential generating function for permutations with all valleys even and all peaks odd. In the next sections, we give a more direct proof of this fact. \subsection{Permutations with prescribed descent sets and alternating descent sets} First we discuss a connection between counting permutations by descent set and counting permutations by alternating descent set. It is often convenient to represent descent sets of permutations of $[n]$ by compositions of $n$, i.e., sequences of positive integers with sum~$n$. To a subset $S\subseteq [n-1]$ with elements $s_1\underset{L_{2}}{\underbrace{i_{L_{1}+1}\leq\cdots\leq i_{L_{1}+L_{2}}}}>\cdots>\underset{L_{k}}{\underbrace{i_{L_{1}+\cdots+L_{k-1}+1}\leq\cdots\leq i_{n}}}. \end{equation} It is clear that \begin{equation} \label{e-htor} \mathbf{h}_{L}=\sum_{K\leq L}\mathbf{r}_{K}, \end{equation} so by inclusion-exclusion, \begin{equation} \mathbf{r}_{L}=\sum_{K\leq L}(-1)^{l(L)-l(K)}\mathbf{h}_{K},\label{e-r} \end{equation} The set $\left\{ \mathbf{r}_{L}\right\} _{L\vDash n}$ is linearly independent, since for $L\neq M$, $\mathbf{r}_{L}$ and $\mathbf{r}_{M}$ have no terms in common. It follows from (\ref{e-htor}) that $\left\{ \mathbf{r}_{L}\right\} _{L\vDash n}$ spans $\Sym _n$, so $\left\{ \mathbf{r}_{L}\right\} _{L\vDash n}$ and $\left\{ \mathbf{h}_{L}\right\} _{L\vDash n}$ are both bases for $\Sym_n$. \subsection{Homomorphisms} We define a homomorphism $\Phi$ from $\Sym$ to $F[[x]]$ by $\Phi(\h_n) = x^n\!/n!$. Then if $L$ is a composition of $n$ we have \begin{equation*} \Phi(\h_L) = \frac{x^{L_1}}{L_1!}\cdots\frac{x^{L_k}}{L_k!} = \binom{n}{L} \frac{x^n}{n!}. \end{equation*} Another description of $\Phi$, which we will not need for our proofs, but which motivates the definition, is that if $f$ is a noncommutative symmetric function then the coefficient of $x^n\!/n!$ in $\Phi(f)$ is the coefficient of $x_1 x_2\cdots x_n$ in the result of replacing $X_1,X_2,\dots$ with commuting variables $x_1, x_2, \dots$. \begin{lem} \label{l-Phi} If $L\vDash n$ then $\Phi(\r_L) = \beta(L)\, x^n\!/n!$. \end{lem} \begin{proof} We have \begin{align*} \Phi(\r_L) &= \Phi\biggl(\sum_{K\leq L}(-1)^{l(L)-l(K)}\mathbf{h}_{K}\biggr), \text{ by \eqref{e-r},} \\ &=\sum_{K\leq L}(-1)^{l(L)-l(K)}\Phi(\mathbf{h}_{K})\\ &=\sum_{K\leq L}(-1)^{l(L)-l(K)}\binom{n}{K}\frac{x^n}{n!}\\ &=\beta(L)\frac{x^n}{n!}, \text{ by \eqref{e-beta}}. \end{align*} \end{proof} We define another homomorphism $\hat\Phi: \Sym\to F[[x]]$ by $\hat\Phi(\h_n)=E_n x^n\!/n!$. Then the following formula for $\hat\Phi(\r_n)$ is proved in exactly the same way as Lemma \ref{l-Phi}: \begin{lem} \label{l-Phihat} If $L\vDash n$ then $\hat\Phi(\r_L) = \hat\beta(L)\, x^n\!/n!$.\qed \end{lem} Lemmas \ref{l-Phi} and \ref{l-Phihat} explain the connection between generating functions for descents and for alternating descents: If an exponential generating function for counting permutations by descents can be obtained by applying $\Phi$ to a noncommutative symmetric function, then applying $\hat\Phi$ will give an analogous generating function for counting permutations by alternating descents. \subsection{Counting words by runs} The next result gives a very general noncommutative symmetric generating function to which we can apply $\Phi$ and $\hat\Phi$. It is Theorem 5.2 of Gessel \cite{gessel-thesis} and is also a noncommutative version of a special case of Theorem 4.2.3 of Goulden and Jackson \cite{MR702512}. See also Jackson and Aleliunas \cite[Theorem 4.1]{MR0450080}. \begin{thm} \label{t-runs}Let $w_{1},w_{2},\dots$ be arbitrary commuting weights and define $a_{0}=1,a_{1},a_{2},\dots$ by \begin{equation} \sum_{n=0}^{\infty}a_{n}z^{n}=\biggl(\sum_{n=0}^{\infty}w_{n}z^{n}\biggr)^{-1},\label{e-cx} \end{equation} where $w_{0}=1$. Then \[ \sum_{L}w_{L}\mathbf{r}_{L}=\biggl(\sum_{n=0}^{\infty}a_{n}\mathbf{h}_{n}\biggr)^{-1} \] where the sum on the left is over all compositions $L$, and $w_{L}=w_{L_{1}}\cdots w_{L_{k}}$ where $L=\left(L_{1},\dots,L_{k}\right)$. \end{thm} \begin{proof} Let us set $a_{n}=-u_{n}$ for $n>0$, and for a composition $K=\left(K_{1},\dots,K_{k}\right)$ let $u_{K}=u_{K_{1}}\cdots u_{K_{k}}$. Then \begin{align} \biggl(\sum_{n=0}^{\infty}a_{n}\mathbf{h}_{n}\biggr)^{-1} & =\biggl(1-\sum_{n=1}^{\infty}u_{n}\mathbf{h}_{n}\biggr)^{-1}\nonumber \\ & =\sum_{K}u_{K}\mathbf{h}_{K}\nonumber \\ & =\sum_{K}u_{K}\sum_{L\leq K}\mathbf{r}_{L}\nonumber \\ & =\sum_{L}\mathbf{r}_{L}\sum_{K\geq L}u_{K}.\label{e-rc} \end{align} By (\ref{e-cx}) we have \[ \sum_{n=0}^{\infty}w_{n}z^{n}=\biggl(1-\sum_{n=1}^{\infty}u_{n}z^{n}\biggr)^{-1} \] so \begin{equation} w_{n}=\sum_{K\vDash n}u_{K}.\label{e-sc} \end{equation} From (\ref{e-sc}) we see that \begin{equation} w_{L}=\sum_{K\geq L}u_{K};\label{e-sK} \end{equation} then the theorem follows from (\ref{e-rc}) and (\ref{e-sK}). \end{proof} \begin{cor} \label{c-runs} Let $m$ be a positive integer. Then \begin{align*} \sum_{L}\mathbf{r}_{L} & =\biggl(1-\mathbf{h}_{1}+\mathbf{h}_{m}-\mathbf{h}_{m+1}+\cdots\biggr)^{-1}\\ & =\biggl(\sum_{n=0}^{\infty}\left(\mathbf{h}_{mn}-\mathbf{h}_{mn+1}\right)\biggr)^{-1} \end{align*} where the sum on the left is over all compositions $L$ with all parts less than $m$.\end{cor} \begin{proof} We apply Theorem \ref{t-runs} with $w_{i}=1$ for $i0$. It is not difficult to see that for $n>0$, \begin{equation*} g(n)=\begin{cases} c(n),&\text{if $n$ is odd,}\\ d(n),&\text{if $n$ is even,} \end{cases} \end{equation*} and thus \begin{equation*} f(n) -g(n)=\begin{cases} c(n),&\text{if $n$ is even,}\\ d(n),&\text{if $n$ is odd.} \end{cases} \end{equation*} Taking Theorem \ref{t-lrun} with $\sum_{n\ge0} w_n z^n = 1+z+z^2$ and $\sum_{n\ge1}v_n z^n = z$ or $z^2$, and then applying the homomorphism $\hat \Phi$, gives the following result. \begin{thm} The exponential generating functions for $c(n)$ and $d(n)$ are \begin{multline*} \sum_{n=0}^\infty c(n) \frac{x^n}{n!} \\ = \sum_{n=0}^{\infty}\left(E_{3n+1}\frac{x^{3n+1}}{\left(3n+1\right)!}-E_{3n+2}\frac{x^{3n+2}}{\left(3n+2\right)!}\right) \biggm/ \sum_{n=0}^{\infty}\left(E_{3n}\frac{x^{3n}}{\left(3n\right)!}-E_{3n+1}\frac{x^{3n+1}}{\left(3n+1\right)!}\right) \end{multline*} and \begin{multline*} \sum_{n=0}^\infty d(n) \frac{x^n}{n!} \\ = \sum_{n=0}^{\infty}\left(E_{3n+2}\frac{x^{3n+2}}{\left(3n+2\right)!}-E_{3n+3}\frac{x^{3n+3}}{\left(3n+3\right)!}\right) \biggm/ \sum_{n=0}^{\infty}\left(E_{3n}\frac{x^{3n}}{\left(3n\right)!}-E_{3n+1}\frac{x^{3n+1}}{\left(3n+1\right)!}\right). \end{multline*} \end{thm} The first few values of $c(n)$ and $d(n)$ are as follows: \[\vbox{\halign{\ \hfil\strut$#$\hfil\ \vrule&&\hfil\ $#$\ \hfil\cr n&0&1&2&3&4&5&6&7&8&9&10&11&12\cr \noalign{\hrule} c(n)&0&1&1&3&9&34&159&853&5249&36369&279711&2367212&21854625\cr d(n)&0&0&1&1&4&16&70&385&2365&16337&125870&1064810&9829820\cr}} \] The generating functions for $c(n)$ and $d(n)$ can also be written in terms of trigonometric and hyperbolic functions: \begin{gather*} \sum_{n=0}^\infty c(n) \frac{x^n}{n!} =\frac{2\sqrt3 \sinh(\frac12 \sqrt3 x)}{3\cos(\frac 12 x) -\sqrt3 \sinh(\frac12 \sqrt 3 x)}\\ \shortintertext{and} \sum_{n=0}^\infty d(n) \frac{x^n}{n!} =\frac{3\sin(\frac12 x) -3\cos(\frac12 x) + 3\cosh(\frac12\sqrt3 x) -\sqrt3\sinh(\frac12\sqrt3 x)}{3\cos(\frac 12 x) -\sqrt3 \sinh(\frac12 \sqrt 3 x)}. \end{gather*} \section{The Alternating Major Index} The \emph{major index} $\maj(\pi)$ of a permutation $\pi$ is the sum of the descents of $\pi$, so for example, the major index of $15243$ is $2+4=6$. Following Remmel \cite{remmel}, we define the \emph{alternating major index} $\altmaj(\pi)$ of $\pi$ to be the sum of the alternating descents of $\pi$. Remmel proved the following result, which reduces to a formula equivalent to \eqref{e-altdes} for $q=1$. \begin{thm} \label{t-remmel} \begin{equation} \label{e-remmel} \sum_{n=0}^\infty \frac{x^n}{n!} \frac{\sum_{\pi\in \S_n} t^{\altdes(\pi)} q^{\altmaj(\pi)}}{(1-t)(1-tq)\cdots (1-tq^n)} =\sum_{k=0}^\infty t^k \prod_{j=0}^k \bigl(\sec(xq^j) +\tan(xq^j)\bigr) \end{equation} \end{thm} We note that multiplying both sides of \eqref{e-remmel} by $1-t$ and taking the limit as $t\to 1$ gives \begin{equation} \label{e-altmaj} \sum_{n=0}^\infty \frac{x^n}{n!} \frac{\sum_{\pi\in \S_n} q^{\altmaj(\pi)}} {(1-q)\cdots (1-q^n)} =\prod_{j=0}^\infty \bigl(\sec(xq^j) +\tan(xq^j)\bigr). \end{equation} We will now derive \eqref{e-remmel} and \eqref{e-altmaj} from formulas for noncommutative symmetric functions. For any composition $L=(L_1,\dots, L_k)$, let us define the major index of $L$ to be $\maj(L) = (k-1)L_1 + (k-2)L_2+\cdots + L_{k-1}$. Then if $\pi$ is a permutation with descent composition $L$, we have $\maj(\pi) = \maj(L)$. Let $H(u) = \sum_{n=0}^\infty \h_n u^n$. (So $\Phi(H(u))= e^{ux}$ and $\hat\Phi(H(u)) = \sec ux + \tan ux$.) Following \cite{ncsf1}, we use the notation \[\leftprod{a\le j \le b}T_j\] to denote the noncommutative product $T_bT_{b-1}\cdots T_a$. Then the following result is Proposition 5.10 of \cite{ncsf1}: \begin{lem} \label{l-ncmaj} \begin{equation*} \leftprod{j\ge0}H(q^j) = \sum_{n=0}^\infty \frac{\sum_{L\vDash n}q^{\maj(L)} \r_L}{(1-q)(1-q^2)\cdots(1-q^n)}. \end{equation*} \end{lem} Formula \eqref{e-altmaj} follows directly from Lemma \ref{l-ncmaj} on applying $\hat\Phi$. Similarly, \eqref{e-remmel} is obtained by applying $\hat\Phi$ to the following result, which is essentially Theorem 8.2 of Gessel \cite{gessel-thesis}. \begin{lem} If $L$ is a nonempty composition, let $\des(L)= l(L) -1$, and if $L$ is the empty composition, let $\des(L) = 0$. Then \begin{equation} \label{e-desmaj} \sum_{k=0}^\infty t^k \leftprod{0\le j\le k} H(q^j) = \sum_{n=0}^\infty \frac{\sum_{L\vDash n} t^{\des(L)}q^{\maj(L)}\r_L}{(1-t)\cdots(1-tq^n)}. \end{equation} \end{lem} \begin{proof} Let us define a \emph{barred word} to be a word in the letters $X_1, X_2,\dots$ and the symbol $|$ (the bar) with the property that $X_i$ is never immediately followed by any $X_j$ with $j