If you remember any high school math, you'll recall the following problem - in how many unique ways can the letters of the word MISSISSIPPI be arranged? Notice there is repetition of some letters - I and S each appear four times, while P appears twice.
Table of Contents
- The Permutation Formula
- The Combination Formula
- Contact24HourAnswers for More Help With Discrete Math
The Permutation formula
Since it's an arrangement, order matters, which is to say that MISSISSIPPI is a different arrangement from IMSSISSIPPI, obtained by switching only the first two letters. If there were no repetition, we would use the permutation formula symbolized by 11P11, and find out there are almost 40 million arrangements (39,916,800 to be exact). Because of the repetition, many of those arrangements are the same, so we have to divide that result by products of factorials for each of the repeating letters. (As a reminder, four factorial, symbolized by 4!, means four times three times two times one, which equals 24.) So, four factorial equals 24, and there are two of those for the letters I and S. For the letter P, we use two factorial which equals two. So, we must divide the huge number above by the product of 24 times 24 times 2:
Without the repetition, of course, there are enormously fewer arrangements. That's all you'll see in most high school math books with regard to permutations with repetition.
What happens, however, if one of your bright students asks the following question: How many unique arrangements can be formed from the letters in the word MISSISSIPPI if you want to form arrangements less than 11 letters long? For example, how many unique five-letter arrangements can be formed? This new problem is not hard, but it will be immeasurably useful to go back to the original problem and look at it in a different way. Let's do that now, and you'll thank me for it later.
The Combination Formula
In the original problem, we wanted to form arrangements using all of the letters in the word. Consider that there are only four different types of letters in the word MISSISSIPPI - in order of decreasing frequency of appearance, they are I, S, P, and M. We can now start the problem by asking: How many ways can we arrange the four I's in the 11 places we must fill? Since the four I's are indistinguishable, we would use the combination formula represented by 11C4, and get 330 ways. There are seven places left to fill, so let's move to the letter S and ask how many ways can we arrange the four S's in those seven spots - this would be 7C4, or 35 ways. There are three ways to arrange the two P's in the three remaining spots, which we get from 3C2, and finally 1C1 gives us one way to put the M in the last remaining spot. The counting principle tells us to multiply those four numbers together to get the total number of ways those letters can be arranged:
Notice that we have obtained the result we got earlier using a single permutation! It is worthwhile to note that the counting principle gave us the unique number of arrangements (permutations) after we used combinations to take care of all the repetition. Very nice, don't you think? In certain situations, then, combinations + the counting principle = permutations.
Now, back to our bright student who has been waiting patiently for an answer. Armed with what we now know, it is easy to answer his question. If we are forming five-letter arrangements, we start again and ask: How many ways can the four I's be arranged to fill the five places? This would be 5C4, giving 5 ways. We have just filled four of the five spots, leaving only one to be filled. There are three remaining types of letters, so we can simply multiply by three and we have our answer:
Contact 24HourAnswers for More Help With Discrete Math
Hopefully, this article will help students and teachers out there who find themselves at the mercy of little combinatorial geniuses who work their way into their classrooms.
For more information, see A Discrete Transition To Advanced Mathematics by Bettina and Thomas Richmond, published by the American Mathematical Society. Chapter four of the text is very helpful on this topic.
Lowell Parker, Ph.D.
Empire State College