In this exercise, we will explore how to enumerate elements of a multiset (a set that contains elements that are not necessarily distinct). Consider the problem of having to determine the number of permutations of the letters in the word CODE. From previous exercises, we know the number of permutations is 4!. What about the word CODEC? Claiming the answer is 5!, as you did for the word CODE, would be incorrect. This is because the letter C appears more than once. If we write the word like this C₁ODEC₂, the following permutation of the word exists: C₂ODEC₁ which is the same as the original word. Since both C’s are identical, it is irrelevant which one is in which position. Therefore we must scale the number of permutations down. To do this, we consider that the order of the two C’s, in whichever spot they appear, does not matter. Sounds familiar? That’s right, we scale down by 2!. So the number of permutations of the word CODEC is:

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

If we were permuting a word with more than one repeated character, we would further scale down the permutations by the count of the other repeated letters. Generally speaking, the number of permutations of a multiset is:

$P(n; r_1, r_2, \ldots, r_k) = \frac{n!}{r_1! r_2! \ldots r_k!}$

Where n is the total size of the multiset and each of r_k‘s represents the count of each element.

Another way of computing this is to “choose” a spot for each element. Consider the word GOOGLE, how many permutations of this word can we have? We “choose” two spots for the G’s, “and” we “choose” two of the remaining spots for the O’s, “and” we “choose” one remaining spot each for the L and the E:

$P(6;2,2,1,1)= \binom{6}{2} \binom{6-2}{2} \binom{4-2}{1} \binom{1}{1} = 180$

Formally:

$P(n; r_1, r_2, r_3 \ldots, r_k)= \binom{n}{r_1} \binom{n-r_1}{r_2} \ldots \binom{n - r_1 - \ldots - r_{k-1}}{r_k}$