Combinatorics

To enumerate is to count. In combinatorics, it is the study of counting objects in different arrangements. The objects are counted and arranged by a set of rules called equivalence relations.

One way to count a set of objects is to ask, "how many different ways can the objects be arranged?" Each change in the original arrangement is called a permutation. For example, changing the order of the songs to be played on a compact disc (CD) player would be a permutation of the regular order of the songs. If there were only two songs on the CD, there would be only two orders, playing the songs in the original order or in reverse order, song two and then song one. With three songs on the CD, there are more than just two ways to play the music. There is the original order, or songs one, two, and three (123) and in reverse order, 321. There are two orders found by flipping the first two songs or the last two songs to get 213 or 132 respectively. There are another two orders, 312 and 231, found by rotating the songs to the right or left. This gives a total of six ways to order the music on a CD with three songs. By just trying different orders, it was intuitively seen how many combinations there were. If the CD had twelve or more songs on it, then this intuitive approach would not be very effective. Trying different arrangements would take a long time, and knowing if all arrangements were found would not be easy. Combinatorics formalizes the way arrangements are found by coming up with general formulas and methods that work for generic cases.

The power of combinatorics, as with all mathematics, is this ability to abstract to a point where complex problems can be solved which could not be solved intuitively. Combinatorics abstracts a problem of this nature in a recursive way. Take the CD example, with three songs. Instead of writing out all the arrangements to find out how many there are, think of the end arrangement and ask, "for the first song in the new arrangement, how many choices are there?" The answer is any three of the songs. There are then two choices for the second song because one of the songs has already been selected. There is only one choice for the last song. So three choices for the first song times two songs for the second choice gives six possibilities for a new arrangement of songs. Continuing in this way, the number of permutations for any size set of objects can be found.

Another example of a permutation is shuffling a deck of playing cards. There are 52 cards in a deck. How many ways can the cards be shuffled? After tearing off the plastic on a brand new deck of cards, the original order of the cards is seen. All the hearts, spades, clubs, and diamonds together and, in each suit, the cards are arranged in numerical order. To find out how many ways the cards can be shuffled, start by moving the first card to any of the 52 places in the deck. Of course, leaving the card in the first place is not moving it at all, which is always an option. This gives 52 shuffles only by moving the first card. Now consider the second card. It can go in 51 places because it can not go in the location of the first card. Again, the option of not moving the card at all is included. That gives a total of 52 × 51 shuffles which equals 2,652 already. The third card can be placed in 50 places and the fourth in 49 places. Continuing this way find to the last card gives a total of 52 × 51 × 50.... × 4 × 3 × 2 × 1 possible shuffles which equals about 81 with sixty-six zeros behind it. A huge number of permutations. Once 51 cards were placed, the last card had only one place it could go, so the last number multiplied was one. Multiplying all the numbers from 52 down to one together is called 52 factorial and is written 52!.