Permutations when some objects are identical

This sub-section extends the permutation formula to the case where some of the objects being arranged are actually IDENTICAL to each other — a situation that arises naturally when arranging the letters of a word like GOOD, INDIA, GEOLOGY, MATHEMATICS, or PHILOSOPHY, where certain letters are repeated and hence not all the letters are genuinely distinct from each other.

The motivating idea is worked through with the small word ODD. First, temporarily treat the two D's as if they were distinguishable, labelling them $D_1$ and $D_2$. Arranging the three 'letters' O, $D_1$, $D_2$ (now all artificially distinct) gives $3!=6$ arrangements: $OD_1D_2,\ OD_2D_1,\ D_1OD_2,\ D_2OD_1,\ D_1D_2O,\ D_2D_1O$. But $D_1$ and $D_2$ are actually IDENTICAL, so several of these six 'different' arrangements are really the same word once the artificial labels are dropped: $OD_1D_2$ and $OD_2D_1$ both simply read ODD; $D_1D_2O$ and $D_2D_1O$ both read DDO; and $D_2OD_1$ and $D_1OD_2$ both read DOD. Since $D_1$ and $D_2$ can be swapped with each other in $2!=2$ ways without changing the actual word, each genuinely distinct word has been counted exactly twice among the six labelled arrangements. So the true number of distinct words is $\dfrac{6}{2!}=\dfrac{6}{2}=3$ — namely ODD, DOD, and DDO.

This motivates the general Theorem: consider a set of $n$ objects where $n_1$ objects are identical (copies of each other) and the remaining $n-n_1$ objects are all distinct from each other and from the repeated group (with $n_1<n$). The number of distinct permutations of these $n$ objects, taken all at a time, is $\dfrac{n!}{n_1!}$.

Proof. Let $m$ denote the true number of distinct arrangements when $n_1$ of the $n$ objects are identical. If, instead, all $n$ objects were treated as fully distinct, the number of permutations would be the familiar $n!$. But each of the $m$ genuinely distinct arrangements corresponds to exactly $n_1!$ different 'labelled' arrangements once the $n_1$ identical objects are artificially treated as distinguishable and rearranged among themselves — exactly as seen in the ODD example above, where each of the 3 true words corresponded to $2!=2$ labelled versions. So $m\times n_1! = n!$, giving $m = \dfrac{n!}{n_1!}$.

Two Remarks extend this to multiple distinct repeated groups. (1) If a set of $n$ objects, not all distinct, has $n_1$ objects of one kind and $n_2$ objects of a second kind (with $n_1+n_2\le n$, the rest distinct), the number of permutations of all $n$ objects taken together is $\dfrac{n!}{n_1!\,n_2!}$ — proved by the identical argument as the single-repeated-group theorem, applied twice. (2) More generally, if there are $k$ distinct kinds of repeated objects, with $n_i$ objects of the $i$-th kind for $i=1,2,\ldots,k$ (and $n_1+n_2+\cdots+n_k\le n$), the number of permutations of all $n$ objects taken together is $\dfrac{n!}{n_1!\,n_2!\cdots n_k!}$.

Solved Example 1. Find the number of permutations of the letters of the word UBUNTU. UBUNTU has 6 letters, in which the letter 'U' is repeated 3 times (the rest — B, N, T — are distinct). By the theorem, the number of permutations is $\dfrac{6!}{3!} = \dfrac{720}{6} = 120$. …