= Alternating-permutation convolution
Let $A_n$ count <alternating permutations> on $n$ labels, with $A_0=1$. For $n\geq1$,
$$
2A_{n+1}=\sum_{k=0}^n\binom nk A_kA_{n-k}.
$$
Count both up-down and down-up <permutations> of $n+1$ labels. Choose the $k$ labels left of the maximum in $\binom nk$ ways. On either side, the comparison next to the maximum fixes which alternating direction is required, giving $A_kA_{n-k}$ choices. Conversely these choices reconstruct exactly one of the two kinds of <alternating permutations>. Replacing each label $a$ by $n+2-a$ interchanges the two kinds, so their combined count is $2A_{n+1}$.
For $n=1$, the identity reads $2A_2=A_0A_1+A_1A_0=2$. The restriction $n\geq1$ matters: on one label, the two alternating conventions describe the same <permutation>, and substitution of $n=0$ would incorrectly give $2A_1=A_0^2$.
Back to article page