This is a sketch of a solution by my student Yan Zhuang and me. A paper with all the details (and further results) can be found on the arXiv at http://arxiv.org/abs/1408.1886. We find the exact exponential generating function for counting these permutations and derive the asymptotics from it.

First, there is no reason from the enumerative point of view to consider only permutations of odd length. So let $u_n$ be the number of permutations of $\{1,2,\dots, n\}$ in which every peak is even and every valley is odd, where a peak of $\pi\in S_n$ is an $i$, with $1<i<n$, such that $\pi(i-1)<\pi(i)>\pi(i+1)$, and valleys are defined similarly. The first few values of $u_n$ are $u_0=1$, $u_1=1$, $u_2=2$,$u_3=4$, $u_4=13$, $u_5=50$, $u_6=229$. Let \begin{equation} U(x) = \sum_{n=0}^\infty u_n \frac{x^n}{n!}.\end{equation} The nicest formula for $U(x)$ is \begin{equation} U(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}, \tag{1}\end{equation} where $$\sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x.$$ A formula equivalent to (1) which is more useful for asymptotics is \begin{equation}U(x) = \frac{3\sin\frac x 2 + 3\cosh \frac {\sqrt3}{2} x} {3\cos \frac x 2 -\sqrt 3\sinh \frac{\sqrt3}{2} x}. \tag{2}\end{equation}

Since $U(x)$ is meromorphic with a single simple pole on its circle of convergence, at $x=\alpha:=1.299828316\cdots$, we find by standard techniques that $u_n/n!$ is asymptotic to $2\beta^{n+1}$, where $\beta:=\alpha^{-1}=.7693323708\cdots$.

Formula (2) can be proved by finding a recurrence for $u_n$, converting it to a differential equation, and solving it. (We need to use an auxiliary sequence, and consider even and odd $n$ separately, so we actually get a system of four differential equations.)

We can give a more conceptual proof of (1). We first note that the similar-looking exponential generating function \begin{equation}\left( 1-x + \frac{x^3}{3!}-\frac{x^4}{4!}+\frac{x^6}{6!}-\frac{x^7}{7!} +\cdots\right)^{-1}\tag{3}\end{equation} (OEIS sequence A049774) counts permutations with no increasing run of length greater than 2.

We may define an alternating run of a permutation $\pi$ to be a maximal subsequence of the form $\pi(2i)<\pi(2i+1)>\pi(2i+2)<\cdots\mathrel{<\atop >}\pi(j)$ or $\pi(2i+1)>\pi(2i+2)<\pi(2i+3)>\cdots \mathrel{<\atop >}\pi(j)$. Then the permutations counted by $u_n$ are permutations with no alternating run of length greater than 2, and (1) can be proved in a way that is analogous to the proof of (3).

Formulas involving the numbers $E_n$ and “alternating descents”, using the same basic idea, have been proved by Denis Chebikin, Variations on descents and inversions in permutations, Electronic J. Combin. 15 (2008), Research Paper R132.

This is a sketch of a solution by my student Yan Zhuang and me. A paper with all the details (and further results) can be found in Counting permutations by alternating descents, Electronic J. Combin. 21 (4) (2014), Paper #P4.23.

We find the exact exponential generating function for counting these permutations and derive the asymptotics from it.

First, there is no reason from the enumerative point of view to consider only permutations of odd length. So let $u_n$ be the number of permutations of $\{1,2,\dots, n\}$ in which every peak is even and every valley is odd, where a peak of $\pi\in S_n$ is an $i$, with $1<i<n$, such that $\pi(i-1)<\pi(i)>\pi(i+1)$, and valleys are defined similarly. The first few values of $u_n$ are $u_0=1$, $u_1=1$, $u_2=2$,$u_3=4$, $u_4=13$, $u_5=50$, $u_6=229$. Let \begin{equation} U(x) = \sum_{n=0}^\infty u_n \frac{x^n}{n!}.\end{equation} The nicest formula for $U(x)$ is \begin{equation} U(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}, \tag{1}\end{equation} where $$\sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x.$$ A formula equivalent to (1) which is more useful for asymptotics is \begin{equation}U(x) = \frac{3\sin\frac x 2 + 3\cosh \frac {\sqrt3}{2} x} {3\cos \frac x 2 -\sqrt 3\sinh \frac{\sqrt3}{2} x}. \tag{2}\end{equation}

Since $U(x)$ is meromorphic with a single simple pole on its circle of convergence, at $x=\alpha:=1.299828316\cdots$, we find by standard techniques that $u_n/n!$ is asymptotic to $2\beta^{n+1}$, where $\beta:=\alpha^{-1}=.7693323708\cdots$.

Formula (2) can be proved by finding a recurrence for $u_n$, converting it to a differential equation, and solving it. (We need to use an auxiliary sequence, and consider even and odd $n$ separately, so we actually get a system of four differential equations.)

We can give a more conceptual proof of (1). We first note that the similar-looking exponential generating function \begin{equation}\left( 1-x + \frac{x^3}{3!}-\frac{x^4}{4!}+\frac{x^6}{6!}-\frac{x^7}{7!} +\cdots\right)^{-1}\tag{3}\end{equation} (OEIS sequence A049774) counts permutations with no increasing run of length greater than 2.

We may define an alternating run of a permutation $\pi$ to be a maximal subsequence of the form $\pi(2i)<\pi(2i+1)>\pi(2i+2)<\cdots\mathrel{<\atop >}\pi(j)$ or $\pi(2i+1)>\pi(2i+2)<\pi(2i+3)>\cdots \mathrel{<\atop >}\pi(j)$. Then the permutations counted by $u_n$ are permutations with no alternating run of length greater than 2, and (1) can be proved in a way that is analogous to the proof of (3).

Formulas involving the numbers $E_n$ and “alternating descents”, using the same basic idea, have been proved by Denis Chebikin, Variations on descents and inversions in permutations, Electronic J. Combin. 15 (2008), Research Paper R132.

This is a sketch of a solution by my student Yan Zhuang and me. (We hope to write up a more detailed account later.) We find the exact exponential generating function for counting these permutations and derive the asymptotics from it.

First, there is no reason from the enumerative point of view to consider only permutations of odd length. So let $u_n$ be the number of permutations of $\{1,2,\dots, n\}$ in which every peak is even and every valley is odd, where a peak of $\pi\in S_n$ is an $i$, with $1<i<n$, such that $\pi(i-1)<\pi(i)>\pi(i+1)$, and valleys are defined similarly. The first few values of $u_n$ are $u_0=1$, $u_1=1$, $u_2=2$,$u_3=4$, $u_4=13$, $u_5=50$, $u_6=229$. Let \begin{equation} U(x) = \sum_{n=0}^\infty u_n \frac{x^n}{n!}.\end{equation} The nicest formula for $U(x)$ is \begin{equation} U(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}, \tag{1}\end{equation} where $$\sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x.$$ A formula equivalent to (1) which is more useful for asymptotics is \begin{equation}U(x) = \frac{3\sin\frac x 2 + 3\cosh \frac {\sqrt3}{2} x} {3\cos \frac x 2 -\sqrt 3\sinh \frac{\sqrt3}{2} x}. \tag{2}\end{equation}

Since $U(x)$ is meromorphic with a single simple pole on its circle of convergence, at $x=\alpha:=1.299828316\cdots$, we find by standard techniques that $u_n/n!$ is asymptotic to $2\beta^{n+1}$, where $\beta:=\alpha^{-1}=.7693323708\cdots$.

Formula (2) can be proved by finding a recurrence for $u_n$, converting it to a differential equation, and solving it. (We need to use an auxiliary sequence, and consider even and odd $n$ separately, so we actually get a system of four differential equations.)

We can give a more conceptual proof of (1). We first note that the similar-looking exponential generating function \begin{equation}\left( 1-x + \frac{x^3}{3!}-\frac{x^4}{4!}+\frac{x^6}{6!}-\frac{x^7}{7!} +\cdots\right)^{-1}\tag{3}\end{equation} (OEIS sequence A049774) counts permutations with no increasing run of length greater than 2.

We may define an alternating run of a permutation $\pi$ to be a maximal subsequence of the form $\pi(2i)<\pi(2i+1)>\pi(2i+2)<\cdots\mathrel{<\atop >}\pi(j)$ or $\pi(2i+1)>\pi(2i+2)<\pi(2i+3)>\cdots \mathrel{<\atop >}\pi(j)$. Then the permutations counted by $u_n$ are permutations with no alternating run of length greater than 2, and (1) can be proved in a way that is analogous to the proof of (3).

Formulas involving the numbers $E_n$ and “alternating descents”, using the same basic idea, have been proved by Denis Chebikin, Variations on descents and inversions in permutations, Electronic J. Combin. 15 (2008), Research Paper R132.

This is a sketch of a solution by my student Yan Zhuang and me. A paper with all the details (and further results) can be found on the arXiv at http://arxiv.org/abs/1408.1886. We find the exact exponential generating function for counting these permutations and derive the asymptotics from it.

First, there is no reason from the enumerative point of view to consider only permutations of odd length. So let $u_n$ be the number of permutations of $\{1,2,\dots, n\}$ in which every peak is even and every valley is odd, where a peak of $\pi\in S_n$ is an $i$, with $1<i<n$, such that $\pi(i-1)<\pi(i)>\pi(i+1)$, and valleys are defined similarly. The first few values of $u_n$ are $u_0=1$, $u_1=1$, $u_2=2$,$u_3=4$, $u_4=13$, $u_5=50$, $u_6=229$. Let \begin{equation} U(x) = \sum_{n=0}^\infty u_n \frac{x^n}{n!}.\end{equation} The nicest formula for $U(x)$ is \begin{equation} U(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}, \tag{1}\end{equation} where $$\sum_{n=0}^\infty E_n \frac{x^n}{n!} = \sec x + \tan x.$$ A formula equivalent to (1) which is more useful for asymptotics is \begin{equation}U(x) = \frac{3\sin\frac x 2 + 3\cosh \frac {\sqrt3}{2} x} {3\cos \frac x 2 -\sqrt 3\sinh \frac{\sqrt3}{2} x}. \tag{2}\end{equation}

Since $U(x)$ is meromorphic with a single simple pole on its circle of convergence, at $x=\alpha:=1.299828316\cdots$, we find by standard techniques that $u_n/n!$ is asymptotic to $2\beta^{n+1}$, where $\beta:=\alpha^{-1}=.7693323708\cdots$.

Formula (2) can be proved by finding a recurrence for $u_n$, converting it to a differential equation, and solving it. (We need to use an auxiliary sequence, and consider even and odd $n$ separately, so we actually get a system of four differential equations.)

We can give a more conceptual proof of (1). We first note that the similar-looking exponential generating function \begin{equation}\left( 1-x + \frac{x^3}{3!}-\frac{x^4}{4!}+\frac{x^6}{6!}-\frac{x^7}{7!} +\cdots\right)^{-1}\tag{3}\end{equation} (OEIS sequence A049774) counts permutations with no increasing run of length greater than 2.

We may define an alternating run of a permutation $\pi$ to be a maximal subsequence of the form $\pi(2i)<\pi(2i+1)>\pi(2i+2)<\cdots\mathrel{<\atop >}\pi(j)$ or $\pi(2i+1)>\pi(2i+2)<\pi(2i+3)>\cdots \mathrel{<\atop >}\pi(j)$. Then the permutations counted by $u_n$ are permutations with no alternating run of length greater than 2, and (1) can be proved in a way that is analogous to the proof of (3).

Formulas involving the numbers $E_n$ and “alternating descents”, using the same basic idea, have been proved by Denis Chebikin, Variations on descents and inversions in permutations, Electronic J. Combin. 15 (2008), Research Paper R132.