Past exam of the mathematics course of the University of Cambridge / 2023 / ia / Paper 4 / 1F / b / 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 $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ 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

Solved by gpt-5.6-sol high.