Permutations with Identical Elements

Section 3.3 Permutations with Identical Elements

Recall that the number of permutations of \(n\) unique objects \(n\) at a time is \(n!\text{.}\) However, if some of those \(n\) objects are identical, this number is reduced, because some permutations are indistinguishable.

Example 3.3.1.

For example, consider the number of permutation of letters in the word \(WOOD\text{.}\) If all the letters were distinct, the number of arrangements would be \(4! = 24\text{.}\) However, \(WOOD\) contains two \(O\)s (say, \(O_1\) and \(O_2\)) and so the permutation \(WO_1 O_2 D\) is indistinguishable to \(WO_2 O_1 D\) (they are both \(WOOD\)). When counting only unique permutations, these two (\(2! = 2\) are counted as one. Each permutation of \(WO_1 O_2 D\) (with subscripts) can be arranged in groups of \(2 = 2!\text{,}\) where every group corresponds to a single permutation of \(WOOD\) (without subscripts). Then, the number of permutations of \(WOOD\) is,

\begin{equation*} \frac{4!}{2!} = 4 \cdot 3 = 12 \end{equation*}

\begin{equation*} \begin{array}{c|c|c} \amp \text{unique} \amp \text{non-unique} \\ \amp \text{permutations} \amp \text{permutations} \\ \hline 1 \amp WOOD \amp \\ \hline 2 \amp WDOO \amp \\ \hline 3 \amp WODO \amp \\ \hline 4 \amp OWOD \amp \\ \hline 5 \amp OWDO \amp \\ \hline 6 \amp OOWD \amp \\ \hline 7 \amp OODW \amp \\ \hline 8 \amp ODWO \amp \\ \hline 9 \amp ODOW \amp \\ \hline 10 \amp DWOO \amp \\ \hline 11 \amp DOWO \amp \\ \hline 12 \amp DOOW \amp \end{array} \end{equation*}

Example 3.3.2.

Similarly, consider the word \(BUBBLE\text{.}\) There are three \(B\)s (say \(B_1, B_2, B_3\)) and so the 6 permutations,

\begin{equation*} B_1 U B_2 B_3 LE \quad B_1 U B_3 B_2 LE \quad B_2 U B_1 B_3 LE \quad B_2 U B_3 B_1 LE \quad B_3 U B_1 B_2 LE \quad B_3 U B_2 B_1 LE \end{equation*}

are all indistinguishable. In general, any rearrangement of these B's will not create a new permutation. There are \(6 = 3!\) ways to arrange these 3 B's, so the number of permutations is,

\begin{equation*} \frac{6!}{3!} = 6 \cdot 5 \cdot 4 = 120 \end{equation*}

More generally,

Subsection 3.3.1 Permutations with Identical Objects

Theorem 3.3.3. Permutation with identical objects.

The number of permutations of \(n\) objects with \(n\) identical objects is,

\begin{equation*} \boxed{\frac{n!}{r!}} \end{equation*}

This can be extended to permutations with multiple groups of identical objects.

Example 3.3.4.

Consider 5 soup cans, made up of 3 noodle soup cans and 2 tomato soup cans. The 3 noodle soup cans are identical, so they can be arranged in \(3! = 6\) indistinguishable ways. Similarly, the 2 tomato soup cans can be arranged in \(2! = 2\) indistinguishable ways. Then, the number of permutations is,

\begin{equation*} \frac{5!}{3! 2!} = \frac{5 \cdot 4}{2} = 10 \end{equation*}

Theorem 3.3.5. Permutations with multiple groups of identical objects.

The number of permutations of \(n\) objects with \(n_1\) identical objects of one kind, \(n_2\) identical objects of another kind, and so on for \(k\) kinds of objects, is,

\begin{equation*} \boxed{\frac{n!}{n_1! n_2! \cdots n_k!}} \end{equation*}

Here, \(n_1 + n_2 + \dots + n_k = n\text{.}\)

Note that if all of the objects are unique, then \(n_i = 1\) for every \(i\text{,}\) and the expression simplifies to \(n!\text{,}\) as from before.

Subsection 3.3.2 Anagrams

An anagram is a word or phrase formed by rearranging (i.e. permuting) the letters of a different word or phrase.

So, anagrams are a type of permutation, and so given a certain word (simplify this by not counting multiple words with spaces), how many anagrams of that word exist? Again, simplify things by saying that any arrangement of letters is a “word” whether or not that word is a real word or even pronounceable.

Example 3.3.6.

Determine the number of anagrams that can be formed from the word COMBINATORICS.

There are 13 letters, with O and I both repeated twice. Thus, the number of anagrams is,

\begin{equation*} \frac{13!}{2!2!} = 1556755200 \end{equation*}

Discrete Math