TAOCP 1.2.6 Exercise 60

Exercise 60. [M23] How many $k$-combinations of $n$ objects are there, if repetition is allowed?

Verified: no
Solve time: -

Solution

Let the $n$ objects be labeled $1,2,\ldots,n$. A $k$-combination with repetition allowed is equivalent to a sequence

$$ x_1,x_2,\ldots,x_k $$

such that

$$ 1 \le x_1 \le x_2 \le \cdots \le x_k \le n. $$

For example, when $n=5$ and $k=3$, the combination in which object $2$ is chosen twice and object $4$ once corresponds to

$$ 2,2,4. $$

We shall count these sequences.

Define new variables

$$ y_1=x_1,\qquad y_2=x_2+1,\qquad \ldots,\qquad y_k=x_k+k-1. $$

Since

$$ x_1 \le x_2 \le \cdots \le x_k, $$

we have

$$ y_1<y_2<\cdots<y_k. $$

Also,

$$ 1\le y_1, $$

and

$$ y_k=x_k+k-1\le n+k-1. $$

Hence each multiset combination corresponds uniquely to an ordinary $k$-combination chosen from the $n+k-1$ integers

$$ 1,2,\ldots,n+k-1. $$

Conversely, given integers

$$ 1\le y_1<y_2<\cdots<y_k\le n+k-1, $$

define

$$ x_i=y_i-(i-1). $$

Then

$$ 1\le x_1\le x_2\le\cdots\le x_k\le n, $$

so we recover a unique $k$-combination with repetition allowed.

Therefore the number of such combinations equals the number of ordinary $k$-combinations of $n+k-1$ objects:

$$ \boxed{\binom{n+k-1}{k}}. $$

By the symmetry condition (6), this is also

$$ \boxed{\binom{n+k-1}{n-1}}. $$

∎