1.2.4 Combinations with Unlimited Repetition

Consider the selection of k objects from as set of n objects where order does not matter and repetition is allowed.
Any such selection is called a k-combination with unlimited repetition of a set of n objects

The number of k-combination with unlimited repetition of a set of n objects,
= The number of non-negative integer solutions of x1+x2+⋯+xn=k
= The number of distributions of k integer balls into n distinct boxes
= The number of sequences of length k+n−1 consisting of k 0’s and n−1 |’s

Proof

Let A be the set of all k-combinations with unlimited repetition of a set X with n elements.
Let B be the set of all non-negative integer solutions of x1+x2+⋯+xn=k
Let C be the set of all distributions of k identical balls into n distinct boxes
Let D be the set of all sequences of length k+n−1 consisting of k 0’s and n−1 |’s

Show that |A|=|B|=|C|=|D|

Prove |A|=|B|

Let X={1,2,…,n}. Suppose that we selected x1 objects of type 1, x2 objects of type 2, … and xn objects of type n. Then, for an n-tuple of integers (x1,x2,…,xn) the following holds:
for every i∈{1,…,n},xi≥0, and x1+x2+⋯+xn=k
Essentially, B is a representation of the k-combinations, i.e. if X={a,b,c} and k=3 then B1 could be:
(3,0,0) or (1,2,0) or (1,1,1) or …
these would represent the k-combinations:
(a,a,a) or (a,b,b) or (a,b,c)

And due to this, there is a one-to-one correspondence between A and B,
⟹|A|=|B|

Prove |B|=|C|

Consider a distribution of k identical boxes in n distinct boxes, where box 1 gets x1 balls, box 2 get x2 balls, … and box n gets xn balls. Then for an n-tuple of integers (x1,x2,…,xn) the following holds
for every i∈{1,…,n},xi≥0, and x1+x2+⋯+xn=k
Each n-tuple of non-negative integers that is a solution of the linear equation x1+x2+⋯+xn=k corresponds to exactly one distribution of k identical balls into n distinct boxes, and vice versa

So there is a one-to-one correspondence between B and C
⟹|B|=|C|

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)=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)=(k+n−1)!k!(n−1)!

Prove |C|=|D|

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)=(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)=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)=(k+n−1)!k!(n−1)!

Examples
Example

Find the number of non-negative integer solutions of x1+x2+⋯+x5=30

Model as 30 identical balls distributed into 5 distinct boxes
30 0’s
4 |’s
∴C(34,30)=34!30!4!

Example

A bookshelf holds 11 different books in a row. In how many ways can we choose 4 books so that no consecutive books are chosen?

Model as a sequence of 0’s and |’s, | represents a chosen book and 0 represents a book that is not chosen
⟹ Want a sequence of 4 |’s and 7 0’s but cannot have to consecutive |’s

First fill the middle 3 boxes with one book (Don’t need to fill the edges as a book next to the edge isn’t consecutive)
∴ You distribute 4 (0’s) across 5 boxes (4 |’s)

C(4+4,4)=8!4!4!