Combination with repetition

Combinations with repetition are similar to classical combinations, only we allow elements from the support set M to repeat.

Definition and formula

Let's start with a nice example: you walk into a store and want to buy twelve bottled beers on tap. They have a total of four different bottles on the shelf. Now you have several options for buying bottles - for example, you can buy 5 Pilsners, 2 Gambrinus and 1 Staropramen, or you can buy just two bottles from each producer. How many different options are there in total to buy bottles so that you have just twelve?

So we have a basic set M = {Plzeň, Gambrinus, Staropramen, Kozel} and we ask how many k-tic exist where k = 12, which contain elements from the set M and for which the order does not matter?

The derivation of the formula is already rather more complicated than for other combinatorial problems. First, we think of our purchase as a sequence of zeros and ones, such that the number of ones corresponds to the number of bottles purchased from a given manufacturer, and the zero separates the manufacturers. So 111011101111101 tells us that we bought three Pilsners (the first three 1's), then three Gambrinus (0 is the separator, the next three 1's), then five Staropramen (0 is the separator, then five 1's), and finally one Kozl. The whole principle is shown in the following picture:

$$ \underbrace{111}_{Plz}0\underbrace{111}_{Gam}0\underbrace{11111}_{Star}0\underbrace{1}_{Koz} $$

If we wanted to buy 6 Pilsners, 4 Gambrinus, 2 Kozlas and no Staropramen, the sequence would look like this:

$$ \underbrace{111111}_{Plz}0\underbrace{1111}_{Gam}00\underbrace{11}_{Koz} $$

Note that the length of this sequence is always equal to 15 - there must be 12 1s to buy a total of 12 beers. And there must be three separators to be able to separate four different producers. So it remains to calculate how many such sequences of length 15 exist in total that contain exactly three zeros?

We just need to calculate the placement of the zeros - the moment we place 3 zeros among the 12 ones, we have some valid combination of beers. In other words: we have 15 beer hutches in total, and we have to occupy 3 of them with zeros. We automatically occupy the remaining kegs with ones.

This is already a simple combination problem without repetition. We number the 15 sheds with {1, …, 15} and now we always pick three numbers from this set, giving us three indices where we place the zero. For example, for the combination {2, 4, 7} we would get the sequence: 101011011111111. The 2nd, 4th, and 7th indexes are zeros, and the rest are ones. So there is a total of

$$ {15\choose3} = 455 $$

different ways to place zeros in the 15 hutches, and thus 455 different ways to buy 12 beers if we have four different beers.

We can generalize the previous reasoning. If we have a set of elements M of size n and we select from it k-tice, and the elements can repeat, then we compose a sequence of zeros and ones of length n + k − 1 (k ones and n − 1 zeros) and find how many positions we can place n − 1 zeros in, so that the number of combinations with repetition, denoted C'(k, n), is equal to

$$ C'(k, n) = {n+k-1 \choose n-1} = {n+k-1\choose k}. $$

We were able to make the last adjustment because of the basic relationships between the combination numbers.

Solved examples

1. In how many ways can 20 free tickets to the opening night of The Babel be divided among 10 retired women? This is an example for combinations with repetition, because one pensioner can get multiple, potentially all, of the free tickets. We just need to get the right idea of what is n and what is k. In fact, we are choosing 20 combinations of 10 pensioners, in other words, we are creating a sequence of zeros and ones such that the sequence has length 29, contains 20 ones and 9 zeros. So n = 10, k = 20 We get the result:

$$ C'(10, 20) = {10 + 20 - 1 \choose 20} = 10{,}015,005. $$

Sources and further reading

• Combinatorics at cuni.cz
• Bělohlávek, Vychodil: Discrete Mathematics [PDF]