Theorem 1.4

#Theorem

For positive integer $k$ and $n$ , the number of $k$ -combinations with unlimited repetition of a set of $n$ objects is $C (k + n - 1, k) = \frac{(k + n - 1)!}{k! (n - 1)!}$

Proof

Example

In how many ways can 7 identical balls be distributed into 3 distinct boxes?

$k = 7$
$n = 3$
If we model this problem as a set of $7 (k)$ 0’s (for the balls) and $2 (n - 1)$ |’s for the ‘walls’
i.e. 000 | 00 | 00 $⟹$ an example distribution of 3 boxes

To solve this we can do $C (9, 7)$ , choose 7 positions from 9
i.e. 0 0 0 _ 0 0 _ 0 0
Now, we place the |’s in the only available positions (1 way)
$∴$ The answer is $C (9, 7) = \frac{9!}{7! 2!}$
$C (9, 7) = C (9, 2)$
$= C (k + n - 1, k)$
$= C (k + n - 1, n - 1)$
By Theorem 1.2, $C (k + n - 1, k) = \frac{(k + n - 1)!}{k! (n - 1)!}$