5.2: Sorting a Set that Contains Repetition

In the previous section, the new work came from looking at combinations where repetition or replacement is allowed. For our purposes, we assumed that the repetition or replacement was effectively unlimited; that is, the store might only have \(30\) cinnamon raisin bagels, but since Chris was only ordering four bagels, that limit didn’t matter.

In this section, we’re going to consider the situation where there are a fixed number of objects in total; some of them are “repeated” (that is, indistinguishable from one another), and we want to determine how many ways they can be arranged (permuted). This can arise in a variety of situations.

Example \(\PageIndex{1}\)

When Chris gets back from the doughnut store run, he discovers that Mohammed, Jing, Karl, and Sara have joined the study session. He has bought two chocolate doughnuts, three maple doughnuts, and three boston cream doughnuts. In how many ways can the doughnuts be distributed so that everyone gets one doughnut?

Solution

Initially, this looks a lot like a permutation question: we need to figure out the number of ways to arrange the doughnuts in some order, and give the first doughnut to the first student, the second doughnut to the second student, and so on.

The key new piece in this problem is that, unlike the permutations we’ve studied thus far, the two chocolate doughnuts are indistinguishable (as are the three maple doughnuts and the three boston cream doughnuts). This means that there is no difference between giving the first chocolate doughnut to Tom and the second to Mohammed, and giving the first chocolate doughnut to Mohammed and the second to Tom.

One way to solve this problem is to look at it as a series of combinations of the people, rather than as a permutation question about the doughnuts. Instead of arranging the doughnuts, we can first choose which two of the eight people will receive the two chocolate doughnuts. Once that is done, from the remaining six people, we choose which three will receive maple doughnuts. Finally, the remaining three people receive boston cream doughnuts. Thus, the solution is \(\binom{8}{2} \binom{6}{3}\).

Another approach is more like the approach we used to figure out how many \(r\)-combinations there are of \(n\) objects. In this approach, we begin by noting that we would be able to arrange the eight doughnuts in \(8!\) orders if all of them were distinct. For any fixed choice of two people who receive the chocolate doughnuts, there are \(2!\) ways in which those two chocolate doughnuts could have been distributed to them, so in the \(8!\) orderings of the doughnuts, each of these choices for who gets the chocolate doughnuts has been counted \(2!\) times rather than once. Similarly, for any fixed choice of three people who receive the maple doughnuts, there are \(3!\) ways in which these three maple doughnuts could have been distributed to them, and each of these choices has been counted \(3!\) times rather than once. The same holds true for the three boston cream doughnuts. Thus, the solution is \(\dfrac{8!}{(2!3!3!)}\).

Since:

\(\binom{8}{2} \binom{6}{3} = \dfrac{8!}{2!6!} \cdot \dfrac{6!}{3!3!} = \dfrac{8!}{(2!3!3!)} \)

we see that these solutions are in fact identical although they look different.

This technique can be used to give us a general formula for counting the number of ways of arranging \(n\) objects some of which are indistinguishable from each other.

Theorem \(\PageIndex{1}\)

Suppose that:

• there are \(n\) objects;
• for each \(i\) with \(1 ≤ i ≤ m\), \(r_i\) of them are of type \(i\) (indistinguishable from each other); and
• \(r_1 + . . . + r_m = n\).

Then the number of arrangements (permutations) of these \(n\) objects is

\[\dfrac{n!}{r_1!r_2!...r_m!}\]

Proof

We use the same idea as in the solution to Example 5.2.1, above. Either approach will work, but we’ll use the first. There will be \(n\) positions in the final ordering of the objects. We begin by choosing \(r_1\) of these to hold the objects of type \(1\). Then we choose \(r_2\) of them to hold the objects of type \(2\), and so on. Ultimately, we choose the final \(r_m\) locations (in \(\binom{r_m}{r_m} = 1\) possible way) to hold the objects of type \(m\).

Using the product rule, the total number of arrangements is:

\[ \begin{equation} \begin{split} &= \binom{n}{r_1} \binom{n - r_1}{r_2} ... \binom{n - r_1 - ... - r_{m-1}}{r_m} \\ &= \dfrac{n!}{r_1!(n-r_1)!} \cdot \dfrac{(n-r_1)!}{r_2!(n-r_1-r_2)!} \cdot ... \cdot \dfrac{(n-r_1-...-r_{m-1})!}{r_m!0!} \\ &= \dfrac{n!}{r_1!r_2!...r_m!} \end{split} \end{equation} \]

since all of the other terms cancel.

We have notation for this value also.

Note

We use \(\binom{n}{r_1,...,r_m}\) to denote the number of arrangements of \(n = r_1 + . . . + r_m\) objects where for each \(i\) with \(1 ≤ i ≤ m\) we have \(r_i\) indistinguishable objects of type \(i\). Thus,

\[\binom{n}{r_1,...,r_m} = \dfrac{n!}{r_1!...r_m!}\]

This can sometimes apply in unexpected ways.

Example \(\PageIndex{2}\)

Cathy, Akos, and Dagmar will be going into a classroom of \(30\) students. They will each be pulling out four students to work with in a small group setting. In how many ways can the groups be chosen?

Solution

Even though all of the students in the class are distinct, the order in which they get chosen for the group they end up in doesn’t matter. One way of making the selection would be to put the names Cathy, Akos, and Dagmar into a hat (four times each) along with \(18\) blank slips of paper. Each student could choose a slip of paper and would be assigned to the group corresponding to the name they chose. The four slips with Cathy’s name on them are identical, as are the four with Akos’ name, the four with Dagmar’s name, and the \(18\) blank slips.

Thus, the solution to this problem is

\(\binom{30}{4,4,4,18} = \dfrac{30!}{(4!4!4!18)} \)

We could also work this out more directly, by allowing each of Cathy, Akos, and Dagmar to choose four students; Cathy’s choice can be made in \(\binom{30}{4}\) ways; then Akos’ in \(\binom{26}{4}\) ways; then Dagmar’s in \(\binom{22}{4}\) ways, and the product of these is \(\dfrac{30!}{(4!4!4!18)}\).

Exercise \(\PageIndex{1}\)

Evaluate the following problems.

1. Charlie’s teacher gives him a set of magnetic words. He has to make a “poem” using all of them. The words are: on, the, one, up, a, tree, the, child, on, jumps, feels, the, child, with. How many different “poems” can Charlie create, if any ordering of the words is considered to be a poem?
2. When filling the soccer team’s fundraising order, the chocolate company sent six extra boxes of chocolate-covered almonds, three extra boxes of mints, and two extra boxes of plain chocolate. In how many ways can the extras be fairly distributed to the eleven families who ordered chocolates?

Exercise \(\PageIndex{2}\)

Prove the Multinomial Theorem: that

\((x_1 + x_2 + · · · + x_m) = \sum_{k_1 + k_2 + · · · + k_m} \binom{n}{k_1, k_2, . . . , k_m} \prod_{1≤r≤m} x_r^{k_r} \)

[Hint: Choose arbitrary values for \(k_1, k_2, . . . , k_m\) such that

\(k_1 + k_2 + · · · + k_m\)

and evaluate the coefficient of \(x_1^{k_1}x_2^{k_2}...x_m^{k_m}\) that comes from the product on the left-hand side of the equation.