5.1: Unlimited Repetition

For many practical purposes, even if the number of indistinguishable elements in each class is not actually infinite, we will be drawing a small enough number that we will not run out. The bagel shop we visited in Example 2.2.1 is not likely to run out of one variety of bagel before filling a particular order. In standard card games, we never deal enough cards to a single player that they might have all of the cards of one suit and still be getting more cards.

This is the sort of scenario we’ll be studying in this section. The set-up we’ll use is to assume that there are \(n\) different “types” of item, and there are enough items of each type that we won’t run out. Then we’ll choose items, allowing ourselves to repeatedly choose items of the same type as many times as we wish, until the total number of items we’ve chosen is \(r\). Notice that (unlike in Chapter 3), in this scenario \(r\) may exceed \(n\).

We’ll consider two scenarios: the order in which we make the choice matters, or the order in which we make the choice doesn’t matter.

Example \(\PageIndex{1}\)

Chris has promised to bring back bagels for three friends he’s studying with (as well as one for himself). The bagel shop sells eight varieties of bagel. In how many ways can he choose the bagels to give to Jan, Tom, Olive, and himself?

Solution

Here, it matters who gets which bagel. We can model this by assuming that the first bagel Chris orders will be for himself, the second for Jan, the third for Tom, and the last for Olive. Thus, the order in which he asks for the bagels matters.

We actually saw back in Chapter 2 how to solve this problem. It’s just an application of the product rule! Chris has eight choices for the first bagel; for each of these, he has eight choices for the second bagel; for each of these, he has eight choices for the third bagel; and for each of these, he has eight choices for the fourth bagel. So in total, he has \(8^4\) ways to choose the bagels.

OK, so if the order in which we make the choice matters, we just use the multiplication rule. What about if order doesn’t matter?

Example \(\PageIndex{2}\)

When Chris brought back the bagels, it turned out that he’d done a poor job of figuring out what his friends wanted. They all traded around. Later that night, they sent him to the doughnut store, but this time they told him to just bring back eight doughnuts and they’d figure out who should get which. If the doughnut store has five varieties, how many ways are there for Chris to fill this order?

Solution

Let’s call the five varieties chocolate, maple, boston cream, powdered, and jamfilled. One way to describe Chris’ order would be to make a list in which we first write one \(c\) for each chocolate doughnut, then one \(m\) for each maple doughnut, then one \(b\) for each boston cream doughnut, then one \(p\) for each powdered doughnut, and finally one \(j\) for each jam-filled doughnut. Since Chris is ordering eight doughnuts, there will be eight letters in this list. Notice that there’s more information provided by this list than we actually need. We know that all of the first group of letters are \(c\)s, so instead of writing them all out, we could simply put a dividing marker after all of the \(c\)s and before the first \(m\). Similarly, we can put three more dividing markers in to separate the \(m\)s from the \(b\)s, the \(b\)s from the \(p\)s, and the \(p\)s from the \(j\)s. Now we have a list that might look something like this:

\(cc||bbb|ppp\)

(Notice in this possible list, Chris chose no maple or jam-filled doughnuts.)

Now, we don’t actually need to write down the letters \(c\), \(m\), \(b\), and so on, as long as we know how many spaces they take up; we know that any letters that appear before the first dividing marker are \(c\)s, for example. Thus, the following list gives us the same information as the list above:

_ _||_ _ _|_ _ _|

Similarly, if we see the list

|_ _|_ _|_ _ _|_

we understand that Chris ordered no chocolate doughnuts; two maple doughnuts; two boston cream doughnuts; three powdered doughnuts; and one jam-filled doughnut.

So an equivalent problem is to count the number of ways of arranging eight underlines and four dividing markers in a line. This is something we already understand! We have twelve positions that we need to fill, and the problem is: in how many ways can we fill eight of the twelve positions with underlines (placing dividing markers in the other four positions). We know that this can be done in \(\binom{12}{8}\) ways.

This technique can be used to give us a general formula for counting the number of ways of choosing \(r\) objects from \(n\) types of objects, where we are allowed to repeatedly choose objects of the same type.

Theorem \(\PageIndex{1}\)

The number of ways of choosing \(r\) objects from \(n\) types of objects (with replacement or repetition allowed) is

\[\binom{n + r -1}{r}\]

Proof

We use the same idea as in the solution to Example 5.1.2, above. Since there are \(n\) different types of objects, we will need \(n − 1\) dividing markers to keep them apart. Since we are choosing \(r\) objects, we will need \(r\) underlines, for a total of \(n + r − 1\) positions to be filled. We can choose the \(r\) positions in which the objects will go in \(\binom{n+r−1}{r}\) ways, and then (in each case) put dividing markers into the remaining \(n − 1\) positions. Thus, there are \(\binom{n+r−1}{r}\) ways to choose \(r\) objects from \(n\) types of objects, if repetition or replacement of choices is allowed.

Again, we will want to have a short form for this value.

Note

We use \((\binom{n}{r})\) to denote the number of ways of choosing \(r\) objects from \(n\) types of objects (with replacement or repetition allowed),

\[\left(\binom{n}{r} \right) = \binom{n + r - 1}{r}\]

The reason we say “replacement or repetition” is because there is another natural model for this type of problem. Suppose that instead of choosing eight bagels from five varieties, Chris is asked to put his hand into a bag that contains five different-coloured pebbles, and draw one out; then replace it, repeatedly (with eight draws in total). If he keeps count of how many times he draws each of the rocks, the number of possible tallies he’ll end up with is exactly the same as the number of doughnut orders in Example 5.1.2.

The following table summarises some of the key things we’ve learned about counting so far:

Table 5.1.1: The number of ways to choose \(r\) objects from \(n\) objects (or types of objects)
	repetition allowed	repetition not allowed
order matters	\(n^r\)	\(\dfrac{n!}{(n-r)!}\)
order doesn't matter	\((\binom{n}{r})\)	\(\binom{n}{r}\)

Exercise \(\PageIndex{1}\)

Evaluate the following problems.

1. Each of the ten sections in your community band (trombones, flutes, and so on) includes at least four people. The conductor needs a quartet to play at a school event. How many different sets of instruments might end up playing at the event?
2. The prize bucket at a local fair contains six types of prizes. Kim wins \(4\) prizes; Jordan wins three prizes, and Finn wins six. Each of the kids plans to give one of the prizes he has won to his teacher, and keep the rest. In how many ways can their prizes (including the gifts to the teacher) be chosen? (It is important which gift comes from which child.)
3. There are three age categories in the local science fair: junior, intermediate, and senior. The judges can choose nine projects in total to advance to the next level of competition, and they must choose at least one project from each age group. In how many ways can the projects that advance be distributed across the age groups?

Exercise \(\PageIndex{2}\)

Prove the following combinatorial identities:

1. For \(k\), \(n ≥ 1\), \((\binom{n}{k}) = (\binom{n-1}{k}) + (\binom{n}{k-1})\).
2. For \(k\), \(n ≥ 1\), \((\binom{n}{k}) = \binom{n+k−1}{k}\).
3. For \(k\), \(n ≥ 1\), \((\binom{k+1}{n-1}) = \binom{n+k−1}{k}\).
4. For \(1 ≤ n ≤ k\), \((\binom{n}{k-1}) = \binom{k-1}{k-n}\).

Exercise \(\PageIndex{3}\)

Solve the following problems.

1. Find the number of \(5\)-lists of the form \((x_1, x_2, x_3, x_4, x_5)\), where each \(x_i\) is a nonnegative integer and \(x_1 + x_2 + x_3 + x_4 + 3x_5 = 12\).
2. We will buy \(3\) pies (not necessarily all different) from a store that sells \(4\) kinds of pie. How many different orders are possible? List all of the possibilities (using \(A\) for apple, \(B\) for blueberry, \(C\) for cherry, and \(D\) for the other one).
3. Suppose Lacrosse balls come in \(3\) colours: red, yellow, and blue. How many different combinations of colours are possible in a \(6\)-pack of Lacrosse balls?
4. After expanding \((a + b + c + d)^7\) and combining like terms, how many terms are there? [Justify your answer without performing the expansion.