A permutation is an arrangement of a collection of distinct objects. Placing a set of encyclopedias in alphabetical order is one way to "permute" the set of books. When you rearrange cards in your hand, you are making permutations.
Say we are playing a card game and we are dealt 5 cards. Here's a sample hand:
How many different ways can we arrange these cards? Let's pretend that we are arranging the cards from left to right in our hand. We have 5 cards to choose from to put at the leftmost position. So let's select one of them:
We now have 4 cards left to choose from to put in the second position. For example, there are 4 arrangements so far with the Queen first:
There are also 4 arrangements with the 2 first, the 5 first, the 7 first, and the Jack first. In total, there are 5 * 4 = 20 ways to arrange the 2 of the 5 cards. Continuing on, there are 3 possibilities left for each of the 20 ways to arrange the two cards. Thus there are 5 * 4 * 3 = 60 ways to arrange 3 of the 5 cards. Similarly there are 2 cards left that may be selected for the second to last position for each of the arrangements of 3 cards; this means that there are 5 * 4 * 3 * 2 = 120 different ways to arrange four of the five cards. There is only one space left for the card in the last position; it is the one that has not been picked yet! Therefore there are 5 * 4 * 3 * 2 * 1 ways to arrange all of the 5 cards.
You will probably agree that 5 * 4 * 3 * 2 * 1 is an awkward way of representing a number. A more convenient way that mathematicians use is the factorial.
Thus, we may write 5 * 4 * 3 * 2 * 1 as "5!"
Say we have 3 diamonds and 1 club. How many different ways may we arrange these cards with respect to the suit? (The suit means the "type" of card: diamonds, hearts, spades, or clubs)
In this example we are only looking at the suit of the card. Therefore the arrangement
is the same as the arrangement
There are 4 * 3 * 2 * 1 = 4! arrangements of these four cards if there are no restrictions. The arrangements are:
However, we want to find the arrangements with regard to suit! The different arrangements here occur when the King of Clubs is in a different position. Therefore, we must count the *columns* as one arrangement! Mathematically, this is represented as follows:
4!(for the number of total arrangements)
3! * 1!
If one wants to know how many ways to arrange n items, and you have n1 of them are type 1, n2 of type 2, ... , and nr of type r, the number of different ways one can arrange the items is:
n1! * n2! * n3! * ... * nr!
Notice that n1 + n2 + n3 + ... + nr must equal n.
In our above example we had 4 items. 3 of them were diamonds, and 1 of them was a club. Therefore, we can arrange them in
3! * 1!
Say we wanted to determine the number of ways we could arrange the letters in the state that I go to school in, MASSACHUSETTS. If the repeated letters (the A's, the S's, and the T's) were different colors, then there would be 13! different ways to arrange them.
Why? Say "MASSACHUSETTS" looked like this:
Then all of the repeated letters, since they are different colors, are distinct - a blue "S" looks different from a green "S", a red "A" looks different from a white "A", and so on. Since there are 13 distinct objects, there are 13! ways to arrange them.
If "MASSACHUSETTS" looked like this:
Then all the repeated letters appear the same - if someone switched two of the S's, you couldn't tell the difference! Thus, if we wanted to arrange the letters of Massachusetts and the repeated letters were not distinct, then there are
1! * 2! * 4! * 1! * 1! * 1! * 1! * 2!
arrangements. The 2! stands for the 2 repeated A's, the 4! stands for the 4 repeated S's, and the other 2! stands for the 2 repeated T's. There are five 1! because there are five distinct letters (M, C, H, U, E) that are not repeated. This problem is an example of the formula in general (see above for that formula!).