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.
