Counting Arrangements with Multiple Types
What you'll learn: How to count the number of distinct arrangements when you have multiple groups of indistinguishable objects.
The Core Problem
Imagine you have a collection of objects where some are identical to each other. For example, the letters in "MISSISSIPPI" — you have 1 M, 4 I's, 4 S's, and 2 P's. If everything were distinct, there would be 11! ways to arrange them. But because identical objects can swap positions without creating a "new" arrangement, we're overcounting.
Why Regular Permutations Overcount
When objects within a group are indistinguishable, swapping them doesn't produce a different arrangement. If you have n₁ identical objects of type 1, there are n₁! ways to rearrange just those among themselves—all producing the same visible arrangement. The same applies to every group of identical objects.
The Multinomial Coefficient Formula
To count distinct arrangements of n total objects consisting of:
- n₁ objects of type 1
- n₂ objects of type 2
- ...
- nₖ objects of type k
Use:
Number of arrangements = n! / (n₁! × n₂! × ... × nₖ!)
This is the multinomial coefficient, often written as (n; n₁, n₂, ..., nₖ).
Example
For "MISSISSIPPI" (n=11, with 1 M, 4 I's, 4 S's, 2 P's):
Arrangements = 11! / (1! × 4! × 4! × 2!) = 39,916,800 / (1 × 24 × 24 × 2) = 34,650
We divided out all the redundant internal rearrangements within each group of identical letters.
Key Takeaway: When arranging n objects with multiple indistinguishable types, divide n! by the factorial of each group's size to eliminate overcounting from within-group swaps.