A permutation $\pi$ is alternating if $\pi_1 > \pi_2 < \pi_3 > \pi_4 < \dots$. Let $a(n)$ be the number of alternating permutations of size $n$.

(a) Find a recurrence relation for $a(n)$. (b) Evaluate the exponential generating function for $a$.

If I'm understanding this problem correctly, then

$n=1$: $1$ permutation

$n=2$: $1$ permutation

$n=3$: $1$ permutation

$n=4$: $2$ permutations

$n=5$: $5$ permutations


I can't figure out a recurrence relation from this. Any help with both parts of the question is appreciated.

  • 1
    $\begingroup$ shouldn't $n=3$ be 2 permutations? 213 and 312 $\endgroup$ – Chen Wang Apr 7 '14 at 13:36
  • $\begingroup$ @Chen Wang I believe you are correct. $\endgroup$ – User38 Apr 7 '14 at 13:50
  • 1
    $\begingroup$ To help thinking about a recurrence: try counting two numbers separately: the number of alternating permutations of length $n$ that begin with a rise (i.e., $\pi_1 < \pi_2$), and the number that begin with a descent (i.e. $\pi_1 > \pi_2$). Then imagine how you can insert $n+1$ into a permutation of $1$ to $n$. $\endgroup$ – ShreevatsaR Apr 7 '14 at 15:57
  • $\begingroup$ The numbers are tabulated at oeis.org/A000111 and many links and formulas are given. $\endgroup$ – Gerry Myerson Apr 10 '14 at 11:35
  • 1
    $\begingroup$ Good. Then please write up an answer, and post it. Then, when the software permits, you can accept your answer. This keeps the Unanswered Questions list uncluttered, and helps other who come along later with the same question. $\endgroup$ – Gerry Myerson Apr 11 '14 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.