Permutations of Objects with Repetition
What you'll learn: How to count arrangements when some objects in your collection are identical to each other.
The Core Problem
Up until now, we've counted permutations of distinct objects. But what happens when you want to arrange the letters in "MISSISSIPPI"? You can't just use n! because swapping two identical S's doesn't create a new arrangement—it looks exactly the same!
When objects repeat, we're overcounting. The solution is to divide out the redundant arrangements.
The Formula
If you have n total objects where:
- n₁ objects are of type 1 (identical to each other)
- n₂ objects are of type 2 (identical to each other)
- ... and so on for k types
The number of distinct permutations is:
n! / (n₁! × n₂! × ... × nₖ!)
Why It Works
Think of it this way: if all objects were distinct, you'd have n! arrangements. But each group of identical objects can be rearranged among themselves in nᵢ! ways without creating a new visible arrangement. So we divide by each nᵢ! to eliminate the overcounting.
Example: MISSISSIPPI
- Total letters: n = 11
- I appears 4 times: n₁ = 4
- S appears 4 times: n₂ = 4
- P appears 2 times: n₃ = 2
- M appears 1 time: n₄ = 1
Distinct arrangements = 11! / (4! × 4! × 2! × 1!) = 34,650
Without accounting for repetition, we'd wrongly calculate 11! = 39,916,800 arrangements!
Key Takeaway: When arranging n objects with repetitions, divide n! by the factorial of each repetition count to eliminate overcounting: n!/(n₁!n₂!...nₖ!).