= Solution
By part (a), there are $A_{n+1}$ permutations of each alternating type. In an up-down permutation the maximum $n+1$ can occur only at a peak, while in a down-up permutation it can occur only at the complementary positions. Thus, after combining the two types, each possible number $k$ of entries to the left of the maximum occurs once.
Choose those $k$ labels in $\binom nk$ ways. The entries on the two sides must independently alternate, and after order-preserving relabelling can be chosen in $A_k$ and $A_{n-k}$ ways. This <alternating-permutation convolution> is
$$
\boxed{2A_{n+1}=\sum_{k=0}^n\binom nkA_kA_{n-k}.}
$$
Back to article page
