(a) Consider the set of letters How many permutations of this set exist?
(b) Consider the set of letters How many permutations of this set exist?
(c) Generalise the results of the previous two parts. If we have a set of things where a particular thing, say , is repeated times, is repeated times, is repeated times, and so on, find the number of permutations of this set.
The main issue now is that we have a repetition of things. If the things we have were all different, the number of permutations would have been easy to calculate. But now, with repetition of things, the number of permutations will change (it will actually decrease, if you think about it carefully). Let us calculate the permutations in this case from first principles
We have (repeated) “” letters, a “”, a “” and a “”. In all, letters. Consider, for a moment, that the “” s are all different. Let us denote the different “”s by and . Our set of letters is now The number of permutations of this set is simply
If we list down all these permutations, we will see that permutations from this list will correspond to only one permutation, had the “”s been all the same. Why?
Consider any particular permutation with the “” s all different, say If we fix the letters “”, “” and “”, the different “” s can be permuted amongst themselves in ways. We now list down all the permutations so generated on the left hand side in the figure below, and see that these permutations correspond to a single permutation if the “” s were all the same:
Thus, the actual number of permutation with the “”s all same will be
We now have repeated “” s and repeated “” s, and a total of letters. If we for a moment take the “” s and “” s as all different, the total number of permutations of this set of letters would be
However, once we list down these permutations, we will see that (as in the previous part) permutations in this list will correspond to a single permutation if the “”s were all the same. Similarly, permutations in this list will correspond to a single permutation if both the “”s were the same. Thus, the actual number of permutations if “”s and “”s were the same would be
These results can now easily be generalised for this general set and the number of permutations will be
From this example once again, the power of the fundamental principle of counting should be quite evident. Using a logical development/extension of this principle, we see that we’ve been able to solve non-trivial questions like the one above.