Permutations with Repeated Items

Calculates the number of ways to arrange n items where some are identical, n! ÷ (a! × b! × …). List the group sizes separated by commas: for "aaabbc", enter 3, 2, 1.

Explanation

This counts the ways of arranging $n$ items in a row when some of them are identical. Divide the factorial of the total by the factorial of each group of identical items.

\dfrac{n!}{a!\, b!\, c! \cdots}

Here $a, b, c, \ldots$ are the group sizes, and together they add up to $n$ .

Example

Rearrange the six letters of "aaabbc". There are 3 a's, 2 b's and 1 c, so the group sizes to enter are 3, 2, 1.

\dfrac{6!}{3!\,2!\,1!} = \dfrac{720}{6 \times 2 \times 1} = \dfrac{720}{12} = 60

There are 60 distinct arrangements.

Why you divide

If all six letters were different there would be $6! = 720$ orders. But the three a's are indistinguishable: the $3! = 6$ ways of shuffling them among themselves all produce exactly the same visible word.

The same goes for the $2! = 2$ shuffles of the b's. Dividing by $3! \times 2! \times 1! = 12$ removes every duplicate.

Where it is used

Rearranging letters, as in counting the arrangements of "MISSISSIPPI"
Counting shortest paths on a grid: moving 3 steps right and 2 steps up means arranging R R R U U, giving $\dfrac{5!}{3!\,2!} = 10$ routes
Counting patterns of heads and tails in a run of coin tosses

The combination $_nC_r$ is the special case of this formula with only two groups.