TAOCP 5.1.3 Exercise 24

The Eulerian number \(\left\langle {n \atop k} \right\rangle\) is defined as the number of permutations of \(\{1,2,\ldots,n\}\) with exactly \(k\) descents (and therefore exactly \(k+1\) ascending run...

taocpmathematicsalgorithmsvolume-3math-hard

Section 5.1.3: Runs

Exercise 24. [M30] What is the average number of runs in sequences generated as in exercise 5.1.1–18, as a function of $n$?

Verified: yes
Solve time: 48m37s

Setup

The Eulerian number (\left\langle {n \atop k} \right\rangle) is defined as the number of permutations of ({1,2,\ldots,n}) with exactly (k) descents (and therefore exactly (k+1) ascending runs). Exercise 5.1.1-18 describes a method that generates a uniformly random permutation of ({1,\ldots,n}). We are asked to find the average number of runs in such a permutation as a function of (n).

The average number of runs is [ R_n = \frac{1}{n!}\sum_{k=0}^{n-1} (k+1)\left\langle {n \atop k} \right\rangle . ]

Solution

We use the recurrence relation for Eulerian numbers given in the text (Eq. (2)): [ \left\langle {n \atop k} \right\rangle = (k+1)\left\langle {n-1 \atop k} \right\rangle + (n-k)\left\langle {n-1 \atop k-1} \right\rangle, \qquad \text{integer } n>0,; \text{integer } k. ]

Let (D_n = \sum_{k} k\left\langle {n \atop k} \right\rangle) be the total number of descents over all (n!) permutations. Multiply the recurrence by (k) and sum over (k): [ D_n = \sum_k k\left\langle {n \atop k} \right\rangle = \sum_k k(k+1)\left\langle {n-1 \atop k} \right\rangle

  • \sum_k k(n-k)\left\langle {n-1 \atop k-1} \right\rangle. ]

In the second sum, set (j = k-1); then (k = j+1) and (n-k = n-1-j). The sum becomes [ \sum_j (j+1)(n-1-j)\left\langle {n-1 \atop j} \right\rangle. ]

Adding the two sums gives [ D_n = \sum_k \Bigl[ k(k+1) + (k+1)(n-1-k) \Bigr] \left\langle {n-1 \atop k} \right\rangle = \sum_k (k+1)(n-1) \left\langle {n-1 \atop k} \right\rangle. ]

Since (\sum_k \left\langle {n-1 \atop k} \right\rangle = (n-1)!) and (\sum_k k\left\langle {n-1 \atop k} \right\rangle = D_{n-1}), [ D_n = (n-1)\bigl( D_{n-1} + (n-1)! \bigr). ]

The initial condition is (D_1 = 0) (the only permutation of one element has zero descents). We solve the recurrence by iterating: [ \begin{aligned} D_2 &= 1\cdot(0 + 1!) = 1,\ D_3 &= 2\cdot(1 + 2!) = 6,\ D_4 &= 3\cdot(6 + 3!) = 36,\ &;;\vdots \end{aligned} ]

The pattern suggests (D_n = (n-1)! \cdot \frac{n(n-1)}{2}). We prove this by induction. The base case (n=1) holds. Assuming (D_{n-1} = (n-2)! \cdot \frac{(n-1)(n-2)}{2}), then [ \begin{aligned} D_n &= (n-1)\left( (n-2)! \cdot \frac{(n-1)(n-2)}{2} + (n-1)! \right) \ &= (n-1)! \left( \frac{(n-1)(n-2)}{2} + (n-1) \right) \ &= (n-1)! \cdot \frac{(n-1)(n-2 + 2)}{2} \ &= (n-1)! \cdot \frac{n(n-1)}{2}. \end{aligned} ]

Thus the average number of descents is [ \frac{D_n}{n!} = \frac{(n-1)! \cdot n(n-1)/2}{n!} = \frac{n-1}{2}. ]

Since the number of runs equals the number of descents plus one, the average number of runs is [ R_n = 1 + \frac{n-1}{2} = \frac{n+1}{2}. ]

\boxed{\dfrac{n+1}{2}}

Verification

We check the result independently for small (n) using the Eulerian numbers from Table 1.

  • (n=1): (\left\langle {1 \atop 0} \right\rangle = 1). Runs = 1. Average = (1 = (1+1)/2).
  • (n=2): (\left\langle {2 \atop 0} \right\rangle = 1,; \left\langle {2 \atop 1} \right\rangle = 1). Runs: 1 (once), 2 (once). Average = (1.5 = (2+1)/2).
  • (n=3): (\left\langle {3 \atop 0} \right\rangle = 1,; \left\langle {3 \atop 1} \right\rangle = 4,; \left\langle {3 \atop 2} \right\rangle = 1). Runs: 1 (once), 2 (four times), 3 (once). Average = ((1+8+3)/6 = 2 = (3+1)/2).
  • (n=4): (\left\langle {4 \atop 0} \right\rangle = 1,; \left\langle {4 \atop 1} \right\rangle = 11,; \left\langle {4 \atop 2} \right\rangle = 11,; \left\langle {4 \atop 3} \right\rangle = 1). Runs: 1 (once), 2 (11 times), 3 (11 times), 4 (once). Average = ((1+22+33+4)/24 = 60/24 = 2.5 = (4+1)/2).

All checks confirm (\frac{n+1}{2}). An alternative independent derivation uses the symmetry (\left\langle {n \atop k} \right\rangle = \left\langle {n \atop n-1-k} \right\rangle) (Eq. (7)): the average of (k) over (0 \le k \le n-1) is ((n-1)/2), so the average of (k+1) is ((n+1)/2). This matches our result.