Permutations with Repetition
A permutation of a set of objects is an ordering of those objects. When some of those objects are identical, the situation is transformed into a problem about permutations with repetition.
Problems of this form are quite common in practice; for instance, it may be desirable to find orderings of boys and girls, students of different grades, or cars of certain colors, without a need to distinguish between students of the same grade (or cars of the same color, or people of the same gender). In such a case, the problem is implicitly about permutations with repetition; the repeated objects are those that do not need to be distinguished.
Permutations with Repetition
Given a set of \(n\) objects such that there are \(n_1\) identical objects of type 1, \(n_2\) identical objects of type 2, \(\ldots\), and \(n_k\) identical objects of type \(k\), how many distinct permutations of the objects are there? Note that, in this case, all of the objects must appear in a permutation and two orderings are considered different if the two objects in some position \(i\) are non-identical.
If the objects are all distinct, then we have seen that the number of permutations without repetition is \(n!\). For each of these permutations, we can permute the \(n_1\) identical objects of type 1 in \( n_1! \) possible ways; since these objects are considered identical, the arrangement is unchanged. Similarly, we can take any of the \( n_2! \) permutations of the \(n_2\) identical objects of type 2 and obtain the same arrangement. Continuing this argument, we account for these repeated arrangements by dividing by the number of repetitions. This gives the following result for the total number of permutations:
The number of permutations of \(n\) objects with \(n_1\) identical objects of type 1, \(n_2\) identical objects of type 2, \( \ldots\), and \(n_k\) identical objects of type \(k\) is
\[ \frac{n!}{n_1! n_2! \cdots n_k!}.\]
In the case all objects are distinct, we have \(n_1 = n_2 = \cdots = n_d = 1\), and the above theorem shows that the number of permutations is
\[ \frac{n!}{n_1! n_2! \cdots n_d!} = \frac{n!}{1! 1! \cdots 1!} = n!, \]
which we have seen in Permutations without Repetition. Note that we have assumed that the permutation contains all of the objects in the ordering. In the case that we would only like to include some of the objects in the ordering, see Permutations with Restriction.
Basic Examples
In the worked examples of Permutations without Repetition, we saw that if Lisa has \(n\) different ornaments, then she can arrange them in \(n!\) different ways on her mantle. What happens if Lisa instead has some ornaments that are identical? How many ways can Lisa arrange ornaments on her mantle if she has 2 identical cat ornaments, 3 identical dog ornaments, 1 rabbit, 1 penguin, and 1 koala ornament?
In total, there are 8 objects, and if the objects were considered to be distinct, there are \( 8! \) ways to arrange them on the mantle. For any arrangement, we can take any of the \( 2! \) permutations of the cat ornaments and obtain the same arrangement. Similarly, we can take any of the \( 3! \) permutations of dog ornaments and obtain the same arrangement. Thus, to account for these repeated arrangements, we divide by the number of repetitions to obtain that the total number of permutations is \( \frac{8!}{3!2!} \). \(_\square\)
How many ways can the letters in the name RAMONA be arranged?
Observe that the letter \(A\) appears twice and all other letters appear once in the word. If we treat the \(A\)'s as distinct from each other \((\)say \( A_1 \) and \( A_2),\) then there are \( 6!= 720 \) ways to rearrange the letters. However, since the letters are the same, we have to divide by \( 2! \) to obtain \( \frac {720}{2!} = 360 \) ways. \(_\square\)
Given a standard deck of cards, there are \(52!\) different permutations of the cards. Given two identical standard decks of cards, how many different permutations are there?
Since the decks of cards are identical, there are 2 identical cards of each type (2 identical aces of spades, 2 identical aces of hearts, etc.). Then \(n_i=2\) for each \(i = 1, 2, \ldots, 52\). The number of different permutations is then
\[ \frac{(52+52)!}{2! 2! \cdots 2!} = \frac{104!}{(2!)^{52} }.\ _\square\]
Intermediate Examples