TAOCP 5.1.3 Exercise 16
We follow the definition of alternating runs given in Exercise 15.
Exercise 16. [M30] Continuing the previous exercise, let $\begin{bmatrix} n \ k \end{bmatrix}$ be the number of permutations of ${1, 2, \ldots, n}$ that have exactly $k$ alternating runs. Find a recurrence relation, by means of which a table of $\begin{bmatrix} n \ k \end{bmatrix}$ can be computed; and find the corresponding recurrence relation for the generating function $G_n(z) = \sum_k \begin{bmatrix} n \ k \end{bmatrix} z^k / n!$. Use the latter recurrence to discover a simple formula for the variance of the number of alternating runs in a random permutation of ${1, 2, \ldots, n}$.
Verified: no
Solve time: 18m
Setup
We follow the definition of alternating runs given in Exercise 15.
For a permutation (a_1a_2\ldots a_n) the alternating runs are the maximal monotonic segments obtained by starting with an ascending run if (a_1<a_2) or a descending run if (a_1>a_2) and switching direction whenever the sequence stops being monotonic.
The number of alternating runs of a permutation of ({1,\ldots,n}) is at most (n-1).
Let (\begin{bmatrix}n\ k\end{bmatrix}) denote the number of permutations of ({1,\ldots,n}) with exactly (k) alternating runs.
The generating function is
[
G_n(z)=\sum_{k}\begin{bmatrix}n\ k\end{bmatrix}\frac{z^k}{n!}.
]
Solution
Recurrence for (\begin{bmatrix}n\ k\end{bmatrix})
Take a permutation (\pi) of ({1,\ldots,n-1}) with (r) alternating runs.
Its successive differences (\operatorname{sign}(\pi_{i+1}-\pi_i)) form a sequence of (n-2) signs grouped into (r) blocks of constant sign, lengths (L_1,\ldots,L_r) ((L_i\ge 1), (\sum L_i=n-2)).
Insert the new maximum element (n) into one of the (n) possible positions (before the first element, between adjacent elements, after the last element).
A careful case analysis of how the number of runs changes shows that, for every permutation with (r) runs, among the (n) insertion positions:
- exactly (r) positions leave the number of runs unchanged ((\Delta=0));
- exactly (2) positions increase the number of runs by (1) ((\Delta=1));
- exactly (n-r-2) positions increase the number of runs by (2) ((\Delta=2)).
This holds independently of the first/last run directions and of the block lengths.
Summing over all permutations with (r) runs therefore yields
[
\begin{bmatrix}n\ k\end{bmatrix}
= k\begin{bmatrix}n-1\ k\end{bmatrix}
- 2\begin{bmatrix}n-1\ k-1\end{bmatrix}
- (n-k)\begin{bmatrix}n-1\ k-2\end{bmatrix}, \qquad n\ge 2, ] with the boundary values (\begin{bmatrix}1\ 0\end{bmatrix}=1) and (\begin{bmatrix}1\ k\end{bmatrix}=0;(k\ne 0)) (so (\begin{bmatrix}2\ 1\end{bmatrix}=2)).
Recurrence for the generating function (G_n(z))
Multiply the recurrence by (z^k/n!) and sum over (k): [ G_n(z)=\frac{z}{n}G_{n-1}'(z)+\frac{2z}{n}G_{n-1}(z) +\frac{z^2}{n}\bigl((n-2)G_{n-1}(z)-zG_{n-1}'(z)\bigr). ] Equivalently, [ n,G_n(z)=z(1-z^2)G_{n-1}'(z)+z\bigl(2+(n-2)z\bigr)G_{n-1}(z). \tag{★} ]
Variance of the number of alternating runs
From (G_n(1)=1) we differentiate (★) at (z=1): [ n,G_n'(1)=2n-2+(n-2)G_{n-1}'(1). ] With (G_1'(1)=0) this solves to (G_n'(1)=\frac{2n-1}{3}) (the mean).
Differentiating (★) twice and evaluating at (z=1) gives, after substituting the mean, [ n,G_n''(1)=(n-4)G_{n-1}''(1)+\frac{8n^2-26n+18}{3}. ] The variance (V_n=G_n''(1)+G_n'(1)-G_n'(1)^2) then satisfies [ n V_n=(n-4)V_{n-1}+\frac{8n-18}{9},\qquad n\ge 3, ] with (V_2=0).
Solving this recurrence for (n\ge 4) (e.g. by multiplying by (\binom{n}{4})) yields the simple formula [ V_n=\frac{16n-29}{90}\qquad(n\ge 4), ] while the initial values are (V_2=0,;V_3=\frac{2}{9}).
[ \boxed{V_n = \frac{16n-29}{90}\ \text{for}\ n\ge 4,\quad V_3=\frac{2}{9},\quad V_2=0} ]
Verification
The recurrence for (\begin{bmatrix}n\ k\end{bmatrix}) was checked by explicit enumeration for (n=3,4):
- (n=3): (\begin{bmatrix}3\ 1\end{bmatrix}=2,;\begin{bmatrix}3\ 2\end{bmatrix}=4).
- (n=4): (\begin{bmatrix}4\ 1\end{bmatrix}=2,;\begin{bmatrix}4\ 2\end{bmatrix}=12,;\begin{bmatrix}4\ 3\end{bmatrix}=10). These match the recurrence and sum to (n!).
The variance formula was verified by computing (V_5) from the distribution obtained via the recurrence:
[
\begin{bmatrix}5\ 1\end{bmatrix}=2,;
\begin{bmatrix}5\ 2\end{bmatrix}=28,;
\begin{bmatrix}5\ 3\end{bmatrix}=58,;
\begin{bmatrix}5\ 4\end{bmatrix}=32,
]
giving mean (3) and variance (\frac{17}{30}=\frac{80-29}{90}).
The recurrence (n V_n=(n-4)V_{n-1}+(8n-18)/9) was also tested for (n=3,4,5,6) and found to hold exactly.
Notes
The key combinatorial observation is that the number of insertion positions producing (\Delta=0,1,2) depends only on the total number of runs (r), not on the detailed block structure.
The symmetry between ascending and descending runs (complementation) guarantees the uniform counts (r,2,n-r-2).
The variance formula (\frac{16n-29}{90}) is exact for (n\ge 4); the small cases (n=2,3) are exceptions because the factor (n-4) in the recurrence vanishes or becomes negative.