An [alternating permutation](https://arxiv.org/abs/0912.4240) of {1, ..., n} is one were π(1) > π(2) < π(3) > π(4) < ... For example: (24153) is an alternating permutation of length 5.


If $E\_n$ is the number of alternating permutations of length n, the $\sec x + \tan x = \sum\_{n \geq 0} E\_n \frac{x^n}{n!}$ is the exponential generating function.


How does one sample the alternating permutations uniformly at random? Rejection sampling would quickly become inefficient since $\frac{E\_n}{n!} \approx \frac{4}{\pi} \left(\frac{2}{\pi} \right)^n$ decays exponentially in *n*.



Random Alternating Permutations
This is very easy - I often teach this in my combinatorics classes. You start with this Pascal type triangle which you need to precompute:
<http://mathworld.wolfram.com/Seidel-Entringer-ArnoldTriangle.html>
(read Arnold's paper referenced there if the pattern is unclear or my survey paper with Postnikov "Increasing Trees and Alternating Permutations" - see my webpage). 


Now note that $a\_{n,i}$, the i-th number in n-th row is the number of alternating permutations with the first letter $\ge i$ (you need to alternate directions). Then you use dynamic programming or simply choose the first letter to be i with probability $a\_{n,i} - a\_{n,i+1}$, which reduces the problem to a alternating permutation of $[n-1]$. I am skipping (easy) details, but I trust you can figure out the rest from here. 


UPDATE (May 10, 2015):  

Apparently, this algorithm requires $O^\ast(n^3)$ time to compute the numbers $a\_{n,i}$ which is not bad. However, if one only wants to compute the number of alternating permutations, there is a faster way: see [this talk](http://jonfest2011.irmacs.sfu.ca/talk/53) by Richard Brent and the slides [here](http://maths-people.anu.edu.au/~brent/pd/tangent.pdf). 


