Permutations of Nondistinguishable Objects

Recall that the number of possible permutations of a set of $n$ distinct elements is given by $n!$:

$\displaystyle n \cdot (n-1) \cdot(n-2) \cdots 2 \cdot 1$

This can be easily tested. The number $1$ can be arranged in just one $1!$ way. The numbers $1$ and $2$ can be arranged in two $2!$ ways: $(1,2)$ and $(2,1)$. The numbers $1$, $2$, and $3$ can be arranged in $3!$ ways: $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$, and $(3,2,1)$. This rule holds true for sets of any size, so long as the elements are all distinct. But what if some elements are repeated?

Repetition of some elements complicates the calculation of permutations, because it allows for there to be multiple ways in which a specific order of elements can be arranged. For example, given the numbers $1$, $3$, and $3$ in a set, there are 2 ways to obtain the order $(3,1,3)$.

To correct for the "multiplicity" of certain permutations, we must divide the factorial of the total number of elements by the product of the factorials of the number of each repeated element. This can generally be represented as:

$\displaystyle \frac {n!}{n_1!n_2!n_3!... }$

Where $n$ is the total number of terms in a sequence, and $n_1$, $n_2$, and $n_3$ represent the number of repetitions of different elements. 

To understand why we would divide by the number of repetitions, consider that $2$elements can be arranged in a total of $2!$ distinct ways, $3$ elements can be arranged in a total of $3!$ distinct ways, and so on. When we encounter multiplicity in a permutation, we must account for it by dividing these possible arrangements out of the total number of permutations that would be possible if all of the elements were distinct.

Example: Consider the set of numbers:

 $\displaystyle (15, 17, 24, 24, 28)$

There are five terms, so $n=5$. However, two of the terms are the same; their value is $24$. Thus, the number of possible distinct permutations in the set is:

$\displaystyle{\frac {5!}{2! }=60}$

The same logic can apply to more complicated systems. 

Example: Consider the set:

$\displaystyle (0, 0, 0, 2, 4, 4, 7, 7, 7, 7, 7, 8, 8)$

In total, there are $13$ elements. These include many repetitions: $0$ is seen 3 times, $4$and $8$ each are observed twice, and there are $5$ instances of the number $7$. Thus, the number of possible distinct permutations can be calculated by:

$\displaystyle \frac {13! }{2!\cdot 2!\cdot 3!\cdot 5! }= 2,162,160$

This logic can be applied to problems involving anagrams of given words. 

Example: Consider how many distinct ways you can order the letters of the word "waterfall."

The word waterfall consists of $9$ letters in total, so $n=9$. The letter "a" appears twice, giving a value of $2$ for $n_{1}$. Similarly, the letter "l" appears twice, yielding $n_{2} = 2$. Thus, the number of distinct permutations for the letters in "waterfall" can be calculated as:

$\displaystyle \frac {9! }{2!\cdot 2!}= 90,720$