7.4 Circular Permutations and Permutations with Similar Elements
Learning Objectives
By the end of this section, you will be able to:
- Count the number of permutations of items arranged in a circle.
- Count the number of permutations when some of the items are identical (indistinguishable).
In this section we address two questions that straight-line permutations cannot:
- In how many different ways can five people be seated in a circle?
- In how many different ways can the letters of the word MISSISSIPPI be arranged?
The first question is a circular permutation; the second is a permutation with similar elements. Both are small tweaks of the multiplication axiom — once you see why the tweak is needed, the formulas drop right out.
7.4.1 Circular Permutations
Suppose we want to seat three people — A, B, and C — around a round table. In a straight line there are \(3! = 6\) arrangements. How many truly different seatings are there around the circle?
Only two. Once you fix where A sits, each of the remaining people has a position relative to A. Rotating the whole table clockwise or counterclockwise doesn't create a new seating — it just spins the same arrangement. The six straight-line permutations collapse into two circular ones: clockwise A → B → C, and clockwise A → C → B.
The rule: in a circular permutation, the first person is a placeholder. Wherever they sit, rotations produce identical arrangements. The remaining \(n - 1\) people can still be arranged in \((n - 1)!\) ways.
Picture the table on a lazy Susan. Spin it, and every guest still has the same neighbors on the same sides — no one has changed seats relative to anyone else. Circular permutations count relative positions, not absolute ones. Any time a problem is about order around a loop (a round table, a merry-go-round, a dance circle), fix one element as the anchor and permute the rest.
A circle of \(n\) items has \(n\) rotations that all look the same, so the straight-line count \(n!\) overcounts by a factor of \(n\). Dividing: \(\dfrac{n!}{n} = (n - 1)!\). Same answer, built from the multiplication axiom you already know.
Source: Applied Finite Mathematics
The number of permutations of \(n\) elements arranged in a circle is
$$(n - 1)!.$$Source: Applied Finite Mathematics
In how many different ways can five people be seated at a circular table?
Solution
Step 1 — Anchor the first person. The first person is a placeholder; their seat doesn't create a new arrangement.
Step 2 — Permute the remaining four. Four seats for four people: \(4 \cdot 3 \cdot 2 \cdot 1\).
| Slot | 1st (anchor) | 2nd | 3rd | 4th | 5th |
|---|---|---|---|---|---|
| Choices | 1 | 4 | 3 | 2 | 1 |
Step 3 — Multiply.
$$(5 - 1)! = 4! = 24.$$Answer: \(24\) seatings.
Source: Applied Finite Mathematics
In how many ways can four couples be seated at a round table if the men and women want to sit alternately?
Solution
Step 1 — Anchor the first person. Say a man sits down first — one choice for the anchor seat.
Step 2 — Alternate by gender. The seat next to the anchor must hold a woman: \(4\) choices. The next seat holds a man: \(3\) choices remaining. Continue alternating, shrinking the pool of each gender as we go.
| Slot | 1st (man) | 2nd (W) | 3rd (M) | 4th (W) | 5th (M) | 6th (W) | 7th (M) | 8th (W) |
|---|---|---|---|---|---|---|---|---|
| Choices | 1 | 4 | 3 | 3 | 2 | 2 | 1 | 1 |
Step 3 — Multiply.
$$1 \cdot 4 \cdot 3 \cdot 3 \cdot 2 \cdot 2 \cdot 1 \cdot 1 = 144.$$Answer: \(144\) seatings.
Source: Applied Finite Mathematics
In how many ways can six people be seated at a round table?
Solution
Anchor one person and arrange the remaining five:
$$(6 - 1)! = 5! = 120 \text{ seatings.}$$7.4.2 Permutations with Similar Elements
Now consider the letters of the word ELEMENT. The word has \(7\) letters, but the letter E appears three times. If we pretend all seven letters are different, we would get \(7!\) permutations — but because the three E's are indistinguishable, many of those "different" arrangements are actually the same.
Label the E's temporarily so we can track them: \(\mathrm{E}_1, \mathrm{L}, \mathrm{E}_2, \mathrm{M}, \mathrm{E}_3, \mathrm{N}, \mathrm{T}\). Take one specific arrangement, say
$$\mathrm{LE_1ME_2NE_3T}.$$If we rearrange only the subscripts on the E's, we get \(3!\) different labeled arrangements that all look the same once we erase the subscripts:
$$\mathrm{LE_1ME_2NE_3T}, \quad \mathrm{LE_1ME_3NE_2T}, \quad \mathrm{LE_2ME_1NE_3T},$$ $$\mathrm{LE_2ME_3NE_1T}, \quad \mathrm{LE_3ME_2NE_1T}, \quad \mathrm{LE_3ME_1NE_2T}.$$All six reduce to the single unlabeled arrangement LEMENET. The same overcounting happens for every unlabeled arrangement. If there are \(n\) distinguishable permutations of ELEMENT, the labeled version has \(n \cdot 3!\) permutations. But we also know the labeled version has exactly \(7!\) permutations. Therefore
$$n \cdot 3! = 7! \quad \implies \quad n = \dfrac{7!}{3!} = 840.$$That division-by-repeats idea generalizes to any word (or ordered set) with repeated items.
When objects repeat, the straight \(n!\) count overcounts by the number of ways you could rearrange the repeats among themselves. Dividing by \(r_1! \cdot r_2! \cdots r_k!\) removes exactly that overcount. You'll see this formula again in binomial and multinomial coefficients — it's the same arithmetic.
Start by treating every item as distinct (\(n!\)). Then, for each group of repeats, un-distinguish them by dividing by the number of internal reorderings (\(r_i!\)). Label-then-cancel is a mental shortcut that works for every problem in this section.
Source: Applied Finite Mathematics
The number of permutations of \(n\) elements taken \(n\) at a time, with \(r_1\) elements of one kind, \(r_2\) elements of another kind, and so on, where \(n = r_1 + r_2 + \cdots + r_k\), is
$$\dfrac{n!}{r_1!\, r_2! \cdots r_k!}.$$This quantity is also called an ordered partition.
Source: Applied Finite Mathematics
Find the number of different permutations of the letters of the word MISSISSIPPI.
Solution
Step 1 — Count letters and repeats. MISSISSIPPI has \(11\) letters: \(4\) S's, \(4\) I's, \(2\) P's, and \(1\) M.
Step 2 — Apply the formula.
$$\dfrac{11!}{4!\, 4!\, 2!\, 1!} = \dfrac{39{,}916{,}800}{24 \cdot 24 \cdot 2 \cdot 1} = 34{,}650.$$Answer: \(34{,}650\) permutations.
Source: Applied Finite Mathematics
If a coin is tossed six times, how many different outcomes consist of 4 heads and 2 tails?
Solution
Step 1 — Reframe as a permutation with similar elements. Ordering the outcomes is the same as arranging the letters HHHHTT — \(6\) items with \(4\) H's and \(2\) T's.
Step 2 — Apply the formula.
$$\dfrac{6!}{4!\, 2!} = \dfrac{720}{24 \cdot 2} = 15.$$Answer: \(15\) outcomes.
Source: Applied Finite Mathematics
In how many different ways can 4 nickels, 3 dimes, and 2 quarters be arranged in a row?
Solution
Step 1 — Treat coins of the same denomination as identical. Nine coins total: \(4\) nickels, \(3\) dimes, \(2\) quarters.
Step 2 — Apply the formula.
$$\dfrac{9!}{4!\, 3!\, 2!} = \dfrac{362{,}880}{24 \cdot 6 \cdot 2} = 1{,}260.$$Answer: \(1{,}260\) arrangements.
Source: Applied Finite Mathematics
A stockbroker wants to assign 20 new clients equally to 4 of its salespeople. In how many different ways can this be done?
Solution
Step 1 — Reframe as an ordered partition. Each salesperson gets \(5\) clients. Think of it as arranging 20 labels — five "A"s, five "B"s, five "C"s, and five "D"s — where the label tells you which salesperson the client goes to.
Step 2 — Apply the formula.
$$\dfrac{20!}{5!\, 5!\, 5!\, 5!} = 11{,}732{,}745{,}024.$$Answer: \(11{,}732{,}745{,}024\) assignments.
Source: Applied Finite Mathematics
♠ Challenge problem. A shopping mall has a straight row of 5 flagpoles at its main entrance plaza. It has 3 identical green flags and 2 identical yellow flags. How many distinct arrangements of flags on the flagpoles are possible?
Solution
Step 1 — Reframe as a permutation of GGGYY. Five letters, \(3\) G's, \(2\) Y's.
Step 2 — Apply the formula.
$$\dfrac{5!}{3!\, 2!} = \dfrac{120}{6 \cdot 2} = 10.$$Step 3 — Enumerate to confirm. Listing the 10 distinct arrangements:
$$\text{GGGYY, GGYGY, GGYYG, GYGGY, GYGYG, GYYGG, YGGGY, YGGYG, YGYGG, YYGGG.}$$Answer: \(10\) arrangements.
Source: Applied Finite Mathematics
How many distinct arrangements can be made from the letters of the word BANANA?
Solution
Step 1 — Count letters and repeats. BANANA has \(6\) letters: \(3\) A's, \(2\) N's, \(1\) B.
Step 2 — Apply the formula.
$$\dfrac{6!}{3!\, 2!\, 1!} = \dfrac{720}{6 \cdot 2} = 60 \text{ arrangements.}$$Summary
Circular Permutations
The number of permutations of \(n\) elements arranged in a circle is
$$(n - 1)!.$$
Permutations with Similar Elements (Ordered Partitions)
The number of permutations of \(n\) elements taken \(n\) at a time, with \(r_1\) elements of one kind, \(r_2\) elements of another kind, and so on, where \(n = r_1 + r_2 + \cdots + r_k\), is
$$\dfrac{n!}{r_1!\, r_2! \cdots r_k!}.$$
Problem Set 7.4
Source: Applied Finite Mathematics
Problems 7.4.1–7.4.8: Do the following problems using circular permutations or permutations with similar elements.
Problem 1. In how many different ways can five children hold hands to play "Ring Around the Rosy"?
Problem 1 Solution
Step 1 — Recognize a circular permutation. Five children holding hands in a ring — rotations don't create new arrangements.
Step 2 — Apply the formula.
$$(5 - 1)! = 4! = 24.$$Answer: \(24\) ways.
Problem 2. In how many ways can three people be made to sit at a round table?
Problem 2 Solution
Step 1 — Circular permutation with \(n = 3\).
$$(3 - 1)! = 2! = 2.$$Answer: \(2\) ways.
Problem 3. In how many different ways can six children ride a merry-go-round with six horses?
Problem 3 Solution
Step 1 — Circular permutation with \(n = 6\). The six horses are distinguishable, but rotations of the merry-go-round are not.
$$(6 - 1)! = 5! = 120.$$Answer: \(120\) ways.
Problem 4. In how many ways can three couples be seated at a round table so that men and women sit alternately?
Problem 4 Solution
Step 1 — Anchor a man. Six people total (3 men, 3 women) alternating around the table. The first man is the placeholder.
Step 2 — Fill by alternating genders. The seat next to the anchor holds a woman (\(3\) choices); next a man (\(2\)); next a woman (\(2\)); next a man (\(1\)); next a woman (\(1\)).
| Slot | 1st (M) | 2nd (W) | 3rd (M) | 4th (W) | 5th (M) | 6th (W) |
|---|---|---|---|---|---|---|
| Choices | 1 | 3 | 2 | 2 | 1 | 1 |
Step 3 — Multiply.
$$1 \cdot 3 \cdot 2 \cdot 2 \cdot 1 \cdot 1 = 12.$$Answer: \(12\) seatings.
Problem 5. In how many ways can six trinkets be arranged on a chain?
Problem 5 Solution
Step 1 — Circular permutation with flip symmetry. A chain can be flipped over, so clockwise and counter-clockwise orderings are the same arrangement. Divide the circular count by \(2\).
Step 2 — Apply the formula.
$$\dfrac{(6 - 1)!}{2} = \dfrac{5!}{2} = \dfrac{120}{2} = 60.$$Answer: \(60\) arrangements.
Problem 6. In how many ways can five keys be put on a key ring?
Problem 6 Solution
Step 1 — Key ring has flip symmetry. Same reasoning as a chain.
$$\dfrac{(5 - 1)!}{2} = \dfrac{4!}{2} = \dfrac{24}{2} = 12.$$Answer: \(12\) arrangements.
Problem 7. Find the number of different permutations of the letters of the word MASSACHUSETTS.
Problem 7 Solution
Step 1 — Count letters and repeats. MASSACHUSETTS has \(13\) letters: \(4\) S's, \(2\) A's, \(2\) T's, and one each of M, C, H, U, E.
Step 2 — Apply the similar-elements formula.
$$\dfrac{13!}{4!\, 2!\, 2!} = \dfrac{6{,}227{,}020{,}800}{24 \cdot 2 \cdot 2} = 64{,}864{,}800.$$Answer: \(64{,}864{,}800\) permutations.
Problem 8. Find the number of different permutations of the letters of the word MATHEMATICS.
Problems 7.4.9–7.4.16: Do the following problems using circular permutations or permutations with similar elements.
Problem 8 Solution
Step 1 — Count letters and repeats. MATHEMATICS has \(11\) letters: \(2\) M's, \(2\) A's, \(2\) T's, and one each of H, E, I, C, S.
Step 2 — Apply the similar-elements formula.
$$\dfrac{11!}{2!\, 2!\, 2!} = \dfrac{39{,}916{,}800}{8} = 4{,}989{,}600.$$Answer: \(4{,}989{,}600\) permutations.
Problem 9. Seven flags are to be flown on seven poles: 3 flags are red, 2 are white, and 2 are blue. How many different arrangements are possible?
Problem 9 Solution
Step 1 — Identify the repeats. Seven flags: \(3\) red, \(2\) white, \(2\) blue.
Step 2 — Apply the similar-elements formula.
$$\dfrac{7!}{3!\, 2!\, 2!} = \dfrac{5{,}040}{6 \cdot 2 \cdot 2} = 210.$$Answer: \(210\) arrangements.
Problem 10. How many different ways can 3 pennies, 2 nickels, and 5 dimes be arranged in a row?
Problem 10 Solution
Step 1 — Identify the repeats. Ten coins: \(3\) pennies, \(2\) nickels, \(5\) dimes (coins of the same denomination are identical).
Step 2 — Apply the similar-elements formula.
$$\dfrac{10!}{3!\, 2!\, 5!} = \dfrac{3{,}628{,}800}{6 \cdot 2 \cdot 120} = 2{,}520.$$Answer: \(2{,}520\) arrangements.
Problem 11. How many four-digit numbers can be made using two 2's and two 3's?
Problem 11 Solution
Step 1 — Four digits: two 2's and two 3's. \(n = 4\), \(r_1 = 2\), \(r_2 = 2\).
$$\dfrac{4!}{2!\, 2!} = \dfrac{24}{4} = 6.$$Answer: \(6\) four-digit numbers.
Problem 12. How many five-digit numbers can be made using two 6's and three 7's?
Problem 12 Solution
Step 1 — Five digits: two 6's and three 7's. \(n = 5\), \(r_1 = 2\), \(r_2 = 3\).
$$\dfrac{5!}{2!\, 3!} = \dfrac{120}{12} = 10.$$Answer: \(10\) five-digit numbers.
Problem 13. If a coin is tossed 5 times, how many different outcomes of 3 heads and 2 tails are possible?
Problem 13 Solution
Step 1 — Reframe as a permutation of HHHTT. \(n = 5\), \(3\) H's, \(2\) T's.
$$\dfrac{5!}{3!\, 2!} = \dfrac{120}{12} = 10.$$Answer: \(10\) outcomes.
Problem 14. If a coin is tossed 10 times, how many different outcomes of 7 heads and 3 tails are possible?
Problem 14 Solution
Step 1 — Reframe as a permutation of HHHHHHHTTT. \(n = 10\), \(7\) H's, \(3\) T's.
$$\dfrac{10!}{7!\, 3!} = \dfrac{3{,}628{,}800}{5{,}040 \cdot 6} = 120.$$Answer: \(120\) outcomes.
Problem 15. If a team plays ten games, how many different outcomes of 6 wins and 4 losses are possible?
Problem 15 Solution
Step 1 — Reframe as a permutation of WWWWWWLLLL. \(n = 10\), \(6\) W's, \(4\) L's.
$$\dfrac{10!}{6!\, 4!} = \dfrac{3{,}628{,}800}{720 \cdot 24} = 210.$$Answer: \(210\) outcomes.
Problem 16. If a team plays ten games, how many different ways can the team have a winning season?
Problem 16 Solution
Step 1 — Define a winning season. More wins than losses in \(10\) games means at least \(6\) wins (\(k = 6, 7, 8, 9, 10\)).
Step 2 — Count each win total using similar elements. For \(k\) wins and \(10 - k\) losses,
$$\dfrac{10!}{k!\,(10 - k)!}.$$| \(k\) wins | Count |
|---|---|
| \(6\) | \(\dfrac{10!}{6!\,4!} = 210\) |
| \(7\) | \(\dfrac{10!}{7!\,3!} = 120\) |
| \(8\) | \(\dfrac{10!}{8!\,2!} = 45\) |
| \(9\) | \(\dfrac{10!}{9!\,1!} = 10\) |
| \(10\) | \(\dfrac{10!}{10!\,0!} = 1\) |
Step 3 — Sum.
$$210 + 120 + 45 + 10 + 1 = 386.$$Answer: \(386\) winning seasons.