Combinations

In my next three articles I am going to look at some games that require the the notion of a combination. I derived this formula in an article I wrote a couple of years ago, but thought it would be a good idea to derive it again and get everyone up to speed before I write these articles.

We begin, not with a combination, but with the idea of a permutation. A permutation is an arrangement of objects in a particular order. Imagine this. You are a curator at an art museum and you have to hang four pictures in four adjacent spots on a wall. How many ways can you do this? Well, there are 4 choices for the leftmost spot and for each of these choices there are three ways to choose a painting for the next spot. Thus there are 4 x 3 or 12 ways to fill the two leftmost spots. This leaves two choices for the next spot and in the last spot there is only one choice. The total number of ways to hang the paintings is, therefore, 4 x 3 x 2 x 1 or 24. If there were k spaces and k pictures the number of ways would equal k x (k-1) x (k-2) … 3 x 2 x 1. Mathematicians have a shorthand notation for this quantity: It is written k! and is called k-factorial. The official definition is that for all k greater than or equal to 1

k! = k x (k - 1)! and 0! = 1 (1)

I realize that the equality 0! = 1 looks a bit strange but I'll explain why this convention is adopted later in the article.

Now suppose that you have seven pictures and you want to hang them in the same four spots. Just as above, there are seven choices for the leftmost spot, then six choices for the next spot, then five for the next and finally four for the last. Hence the number of ways to hang the pictures is 7 x 6 x 5 x 4, which we can write in a compact form as 7!/3!. If there were five spots and nine pictures the answer would be 9 x 8 x 7 x 6 x 5, which we can write as 9!/4!. Let me rewrite these in a slightly different form: 7!/(7 - 4)! and 9!/(9 - 5)!, respectively. We would describe these numbers as the number of permutations of seven objects taken four at a time and 9 objects taken 5 at a time, respectively. The notation is P(7,4) and P(9,5), respectively. I think you can see that the general situation when there are n objects and k spaces is just

P(n, k) = n!/(n-k)! (2)

and is the formula for the number of permutations of n things taken k at a time.

Now suppose we simply want to calculate P(k, k). We know from our earlier discussion that the answer in this case is just k! However, if we substitute k for n in formula (2) we end up with k!/(k - k)! or k!/0!. So you see, in order to make formula (2) work in all situations it is necessary to define 0! = 1.

Now we get to the heart of the matter. Suppose that our n paintings are stored in a warehouse across town from the art museum. Every permutation of these n paintings can be achieved by selecting k of them, loading them in a van, driving them to the museum, and then hanging them in some order in the k spaces available.

How many ways are there to select k paintings from n paintings? I don't know so I'll just write this as C(n, k) and call it the number of combinations of n things taken k at a time; note there is no regard to order. Once these k paintings have been selected and delivered to the museum, we know that there are k! ways to arrange them in the k spots. In other words, we have shown that the number of choices of the k paintings times the number of arrangements of them once chosen is exactly the number of permutations of n things taken k at a time. Thus

C(n, k) x k! = P(n, k) (3)

Aha! we can solve (3) for C(n, k) and from (2) obtain the formula

C(n, k) = n!/[k! x (n - k)!] (4)

Formula (4) is the result we are after. Let's see how it works. Suppose we want to know how many five-card Poker hands there are that can be dealt from a fifty-two card deck. We are asking for C(52, 5). According to formula (4) this is just the number 52!/[5! x 47!] or 52 x 51 x 50 x 49 x 48/(5 x 4 x 3 x 2 x 1); the answer is 2,598,960. See you next month.