TAOCP 3.3.2 Exercise 29

Section 3.3.2: Empirical Tests

Exercise 29. [M35] Continuing exercise 28, find simple expressions for the generating functions $b_{nr}(z) = \sum_{m \ge 0} b_{n,r,0}(m) z^m/m!$, when $r = 0$, 1, and 2.

Verified: no
Solve time: 1m21s

Setup

Let $b_{n,r,s}(m)$ be defined as in Exercise 28: it counts the number of $n$-tuples $(y_1, \ldots, y_n)$ with $0 \le y_j < m$ that have exactly $r$ equal spacings and $s$ zero spacings. Denote by

$b_{n,r,0}(m) = b_{n,r,0}(m),$

the special case with no zero spacings. We are asked to find simple expressions for the exponential generating functions

$b_{nr}(z) = \sum_{m \ge 0} \frac{b_{n,r,0}(m)}{m!} z^m, \quad r = 0, 1, 2.$

We assume the reader is familiar with the standard combinatorial arguments for counting tuples with prescribed spacings (as in the birthday spacings test) and with the definition of generating functions.

Solution

Case $r = 0$

The case $r = 0$ corresponds to the number of $n$-tuples with all distinct spacings and no zero spacings. By Exercise 28(a), $b_{n,0,0}(m)$ is in bijection with the number of partitions of $m$ into at most $n$ positive parts, because each spacing contributes at least 1 to the sum of spacings. Denote the number of such partitions by $p_n(m)$.

The exponential generating function for partitions into at most $n$ parts is well-known:

$$ \sum_{m \ge 0} \frac{p_n(m)}{m!} z^m = \prod_{k=1}^n (1 - z^k)^{-1} \quad \text{(ordinary generating function for partitions, converted to exponential generating function).} $$

However, since we are considering $n$ tuples rather than integer partitions themselves, the appropriate exponential generating function accounts for permutations of the $n$ spacings. Each composition of $m$ into $n$ positive integers corresponds to exactly $n!$ tuples, so we have

$$ b_{n,0,0}(m) = n! \cdot \text{(number of compositions of $m$ into $n$ positive integers)} = n! \binom{m-1}{n-1}, \quad m \ge n. $$

Hence the exponential generating function i