TAOCP 1.2.9 Exercise 16

Exercise 16. [M22] Give a simple formula for the generating function

$$ G_n^{(r)}(z) = \sum_k a_{nkr} z^k, $$

where $a_{nkr}$ is the number of ways to choose $k$ out of $n$ objects, subject to the condition that each object may be chosen at most $r$ times. (If $r=1$, we have $\binom{n}{k}$ ways, and if $r \ge k$, we have the number of combinations with repetitions as in exercise 1.2.6-60.)

Verified: yes
Solve time: 40s

Solution

For each of the $n$ objects, introduce a sequence $b^{(i)}_0,b^{(i)}_1,\ldots,b^{(i)}_r$ defined by

$$ b^{(i)}_j = 1 \quad (0 \le j \le r), \qquad b^{(i)}_j = 0 \quad (j > r). $$

The generating function for the $i$th object is

$$ B_i(z) = \sum_{j \ge 0} b^{(i)}_j z^j = 1 + z + z^2 + \cdots + z^r. $$

A selection of $k$ objects with each object chosen at most $r$ times corresponds to choosing, for each object $i$, a value $j_i$ with $0 \le j_i \le r$ such that

$$ j_1 + j_2 + \cdots + j_n = k. $$

By repeated application of the product rule (6), the generating function for the sequence $\langle a_{nkr} \rangle_k$ is the coefficient sequence of the product

$$ B_1(z) B_2(z) \cdots B_n(z). $$

Since each factor equals $1 + z + \cdots + z^r$, this product is

$$ (1 + z + z^2 + \cdots + z^r)^n. $$

By definition of generating functions, the coefficient of $z^k$ in this expansion equals $a_{nkr}$, hence

$$ G_n^{(r)}(z) = \sum_k a_{nkr} z^k = (1 + z + z^2 + \cdots + z^r)^n. $$

Using the finite geometric sum,

$$ 1 + z + z^2 + \cdots + z^r = \frac{1 - z^{r+1}}{1 - z}, $$

so an equivalent form is

$$ G_n^{(r)}(z) = \left(\frac{1 - z^{r+1}}{1 - z}\right)^n. $$

This completes the derivation.

\boxed{G_n^{(r)}(z) = (1 + z + z^2 + \cdots + z^r)^n = \left(\frac{1 - z^{r+1}}{1 - z}\right)^n} $$∎