Section 1.8 – Circles and Repetition

Suppose you went out to dinner with three friends and the four of you were seated at a table. How many different possible seating arrangements are there?

The order that you sit matters here so this is an example of a permutation. At this point, you might be tempted to pull out the permutation formula and say that there are 4! or 24 but there's a problem with that number. The permutation formula counts {Alice, Bruce, Chris, Denise} as different from {Denise, Alice, Bruce, Chris} but look at what happens if I draw those two arrangements around a circular table.

Are those really different? If you think about who is sitting to the left and right of each person, you'll see that everyone is sitting next to the same people in both arrangements. For example, in both tables Alice has Bruce on her left and Denise on her right. If we start with an arrangement like {Alice, Bruce, Chris, Denise} then every rotation of the table gives us an identical result. Think of it is everyone getting up and moving to the seat on their right, like a game of musical chairs. Because every arrangement has four "rotated" versions around the table our number of arrangements is off by a factor of four which means the actual number is 24 / 4 = 6.

Example 2 illustrates a common approach to counting problems. You start by taking a subgroup (the kids) within a larger group (the entire table) and treat the subgroup as one object. Now, counting the number of arrangements involves two choices:

1. Choose an arrangement of the objects.
2. Choose an arrangement of the subgroup.

If you can count the number of ways that you can make those two choices, then you can get the total number of choices using the Multiplication Rule. In Example 2, the two steps were

(choose an arrangement of the adults and the kids' group)and(choose an arrangement of the kids in the group)

Once we had the number of ways that those two choices could be made, the Multiplication Rule gave us the final result

(total seating arrangements) = (arrangements of the adults and the kids' group) · (arrangements of the kids' group)

One other thing you should notice about Example 2, is that I didn't use the circular permutation formula to find the number of ways that the kids could be arranged. I did this because the kids are being seated in a section of the circle rather than a complete circle.

Identical Objects

All of the situations that we've discussed so far have assumed that all of the things be arranged are unique, for example people or charms on a bracelet. That's not always going to be the case. For example, suppose you wanted to count the number of words that you can make from the letters ARRANGER. Our permutation formula would treat all three R's as different letters to RARANGER would get counted a total of six times, e.g. R₁AR₂ANGER and R₂AR₁ANGER. (R₁ is the first R in ARRANGER and R₂ is the second. I added them so you could see the difference.) We can get the correct number of arrangements using the Multiplication Rule.

First, we can assign the 8 available positions to the 3 R's in ₈C₃ ways.
Second, we can assign the remaining 5 positions to the 2 A's in ₅C₂ ways.
Third, the can assign the 3 remaining positions to the 1 N in ₃C₁ ways.
The 2 remaining positions can be assigned to the G in ₂C₁ ways.
Finally, the 1 remaining position can be assigned to the E in ₁C₁ ways.

According to the Multiplication Rule, we can get the total number of arrangements by multiplying all of those individual choices together:

$$_8C_3 \cdot _5C_2 · _3C_1 · _2C_1 · _1C_1=\frac{8!}{3!5!}\frac{5!}{2!3!}\frac{3!}{1!2!}\frac{2!}{1!1!}\frac{1!}{1!0!} = \frac{8!}{3!2!2!1!1!} = 1,160$$

If the way I canceled going to the second line seems a little odd then take a close look at the bottom numbers: 3, 2, 2, 1 and 1. Notice that those are the number of times that R, A, N, G and E appear in the original word.

If that seems a little confusing, just think back to our example. The numerator is just the factorial of the total number of objects (the eight letters in our example) and the numbers in the denominator are just the number of times that each letter appears in the original word.