Discrete MathCounting

The Division Rule: Repeated Letters and Round Tables

Divide out the orderings that look the same: MISSISSIPPI has 11!/(4! · 4! · 2!) arrangements, and n people around a round table have (n − 1)!.

Not started Jump to practice

The product rule counts arrangements as if every item were different, which is how permutations work. When some arrangements look the same (repeated letters, seats around a round table), the product rule overcounts. If the overcount is the same for every object, one division fixes it.

Key idea

Division rule: if a method produces every object exactly $d$ times, the number of objects is (the method's count) $\div\ d$. Arrangements of $n$ letters with one letter repeated $k_{1}$ times, another $k_{2}$ times, and so on: $\dfrac{n!}{k_{1}!\,k_{2}!\cdots}$. Seatings of $n$ people around a round table (rotations counted as the same): $(n - 1)!$.

Why it works

Give the copies of each letter temporary labels, like $A_{1}A_{2}A_{3}$ in BANANA. Now all letters are different, and there are $6! = 720$ labeled arrangements. Erasing the labels merges arrangements that differ only in how the copies are labeled: $3!$ orders of the A's times $2!$ orders of the N's, the same $12$ for every word. So there are $720 / 12 = 60$ words. For a round table, each seating appears $n$ times among the $n!$ row orders, once for each place where you could cut the circle.
BANANA with labeled copies: every word appears as $3! \cdot 2! = 12$ labeled arrangements.

Worked examples

Worked example: A long word

How many arrangements of MISSISSIPPI are there?
  1. $11$ letters: M once, I four times, S four times, P twice.
  2. Labeled arrangements: $11!$. Each word appears $4! \cdot 4! \cdot 2!$ times.
  3. $\dfrac{11!}{4!\,4!\,2!} = \dfrac{39{,}916{,}800}{24 \cdot 24 \cdot 2} = 34{,}650$.

Answer: $34{,}650$

Worked example: A round table

In how many ways can $6$ people sit around a round table, if seatings that are rotations of each other count as the same?
  1. In a row: $6! = 720$ orders.
  2. Each round seating is counted $6$ times, once for each rotation.
  3. $720 / 6 = 120 = 5!$. Equivalently: seat one person anywhere, then arrange the other $5$ relative to them.

Answer: $120$

Worked example: Rotations and flips

How many different bracelets can be made from $5$ different beads, if a bracelet can be rotated or flipped over?
  1. Around a circle, up to rotation: $(5 - 1)! = 24$.
  2. Flipping turns each arrangement into its mirror image. For $5$ different beads, an arrangement never matches its own mirror image, so each bracelet was counted twice.
  3. $24 / 2 = 12$.

Answer: $12$

Common mistake

Dividing by the wrong factorials, or not dividing for rotations. For BANANA, dividing by $3!$ alone (for the A's) forgets the N's; dividing by $6!/2$ or by $2!$ for each letter makes no sense. And at a round table, $6!$ counts rotations as different seatings. Check: divide by one factorial for each repeated letter, using that letter's count; and ask whether two outcomes your method separates would look identical.
Four people around a table: each seating appears as $4$ row orders.

Practice

Pass with 3 right answers, the last 2 in a row. Each right answer earns 2 XP.

Loading practice…

Builds on

Leads to

Sources and further reading

  • Oscar Levin, Discrete Mathematics: An Open Introduction (3rd ed.), section "Combinations and Permutations"
  • MIT OpenCourseWare 6.042J Mathematics for Computer Science (Lehman, Leighton and Meyer), chapter "Cardinality Rules" (the division rule)
@teddyrookbook GitHub