Combinations with repetition

Combinations with repetition are similar to ordinary combinations, except that we allow the elements of the ground set M to be repeated.

Definition and formula

Let’s start with a nice example. You go into a shop and want to buy twelve bottles of beer for a hiking trip. The shelf has four different beers in total. You have several options for buying them – for example, you could buy 5 lagers, 2 ales, 1 stout and 4 bitters, or you could buy exactly three bottles of each kind. How many different ways are there to buy the bottles so that you end up with exactly twelve?

So we have the ground set M = {lager, ale, stout, bitter}, and we are asking how many selections of k items there are, where k = 12, that contain elements of M and where the order does not matter.

Deriving the formula is quite a bit harder than for the other counting problems. First, we picture our purchase as a sequence of ones and zeros, where the number of ones is the number of bottles bought of a given kind and a zero separates one kind from the next. So 111011101111101 tells us that we bought three lagers (the first three 1s), then three ales (0 is a separator, then three more 1s), then five stouts (0 as a separator, then five 1s) and finally one bitter. The whole idea is shown in the following figure:

$$\underset{\text{Lag}}{\underbrace{111}}0\underset{\text{Ale}}{\underbrace{111}}0\underset{\text{Sto}}{\underbrace{11111}}0\underset{\text{Bit}}{\underbrace{1}}$$

If we wanted to buy 6 lagers, 4 ales, 2 bitters and no stout, the sequence would look like this:

$$\underset{\text{Lag}}{\underbrace{111111}}0\underset{\text{Ale}}{\underbrace{1111}}00\underset{\text{Bit}}{\underbrace{11}}$$

Notice that the length of this sequence is always 15 – there have to be 12 ones so that we buy 12 beers in total, and there have to be three separators so that we can separate the four different kinds. What remains is to work out how many such sequences of length 15 contain exactly three zeros.

It is enough to work out the positions of the zeros – once we have placed 3 zeros among the 12 ones, we have a valid selection of beers. In other words: we have 15 slots in total, and we must fill 3 of them with zeros. The remaining slots are automatically filled with ones.

This is now a simple problem about combinations without repetition. We number the 15 slots with the numbers {1, …, 15} and choose three numbers from this set, which gives us the three positions where we put a zero. For example, the selection {2, 4, 7} gives the sequence 101011011111111. There is a zero in the 2nd, 4th and 7th places and the rest are ones. So there are

$$(\genfrac{}{}{0ex}{}{15}{3})=455$$

different ways to place the zeros into the 15 slots, and therefore also 455 different ways to buy 12 beers when there are four different kinds of beer.

We can generalise this argument. If we have a set M of size n and we choose k items from it, where individual elements may be repeated, then we build a sequence of zeros and ones of length n + k − 1 (k ones and n − 1 zeros) and find out in how many ways we can place the n − 1 zeros. So the number of combinations with repetition is

$$(\genfrac{}{}{0ex}{}{n+k-1}{n-1})=(\genfrac{}{}{0ex}{}{n+k-1}{k}).$$

We were allowed to make the last step thanks to the basic relationships between binomial coefficients.

Worked examples

1. In how many ways can 20 free tickets for a film premiere be shared among 10 pensioners? This is a combinations-with-repetition problem, because one pensioner can receive more than one ticket – potentially all of them. We just need to be careful about what n and k are. We are really choosing 20 items from 10 pensioners, or in other words building a sequence of zeros and ones of length 29 that contains 20 ones and 9 zeros. So n = 10, k = 20. This gives the result:

$$(\genfrac{}{}{0ex}{}{10+20-1}{20})=\mathrm{10,015,005.}$$