A Formula for C(n,k)

We would like to obtain a formula to calculate C(n,k) without writing down Pascal's triangle (although, to be honest, it is generally faster to write down Pascal's triangle than it is to use this formula, especially if you need a number of these binomial coefficients). To do this, we will count the number of subsets of size k in a set of size n.

Before starting the count, we need to look at the difference between ordered sets (arrangements) and unordered sets (selections). In an ordered set, there is a first element, a second element, a third element and so on. Changing which element is considered the first one, and which is considered the second one, and so on, changes the ordered set even if the elements used don't change. Suppose we had three elements A, B and C. The number of ordered sets we could make out of them is 6, i.e., A B C, A C B, B A C, B C A, C A B, and C B A. An easy way to see how these ordered sets come about is to draw a "decision tree" (we usually draw the tree so that it grows down instead of up) like this:

From the start, we draw a branch to each element that can be a first element of the ordered set. From each of these elements, we draw a branch to an element that can be a second element of the ordered set, and then from these we draw branches to elements that can be third elements. At any point in drawing the tree, we must remember that we have used some elements to get to that point, so they are not available to continue with. We are forced to stop extending the tree when there are no more elements that can be used. Now, each path along the branches, starting at the top and always going down to the bottom level corresponds to an ordered set, the ordered set of labels that you pass through as you travel down this path.

Here I've indicated two such paths, the red and the green ones, giving the ordered sets A C B and C A B. It is easy to count the number of paths. At the start, there are 3 branches, and for each of them there are 2 branches that can continue the path (giving a total of 6 = 3(2) two-branch paths), and finally each of these 6 can be continued in only one way so we get a total of 6 = 3(2)(1) paths. If we had started with 4 elements instead of 3, (you should draw the tree for this yourself) we would have gotten 24 = 4(3)(2)(1) paths. Since numbers of this form arise frequently in mathematics, we adopt a special notation for them, we define n! = n(n-1)(n-2) ... (3)(2)(1). So, 3! = 3(2)(1) = 6, 4! = 4(3)(2)(1) = 24, and 5! = 5(4)(3)(2)(1) = 120. This notation is read as "n factorial". To sum up, the number of ordered sets with n elements is then given by n!.

Question: What are 6!, 7! and 8!.

Next we should consider a slightly different problem. How many ordered sets containing only two elements can be made from a set of four elements? It is easy to see that we can answer this question by starting to draw the decision tree for all ordered sets of four elements, but then stopping at the second level.

We see that the answer is 12 = 4(3). If we wanted the number of ordered sets of size 3 made from a set of size 8, there would be 336 = 8(7)(6). In general, the number of ordered sets of size k that can be made from a set of size n, is denoted by P(n,k) and is equal to the number n(n-1)(n-2) ... (n-k+1). Notice that there are exactly k numbers being multiplied here.

Question: Find the values for P(5,2), P(7,4), P(6,1), P(3,3) and P(4,3).

Notice that the earlier problem of finding the number of all ordered sets with n elements is really a special case of this second problem. Another way to say this is that P(n,n) = n!.

We can now find a formula for the C(n,k). We will do this by finding another way to count the number of ordered sets of size k that can be made from a set of size n. Reconsider the problem of finding the number of ordered sets of size 2 in a set of size 4. We can get these sets by first picking a subset of size 2 from the set of size 4 (there are C(4,2) of these), and then ordering the elements of this subset (which can be done in P(2,2) = 2! ways). For each of the C(4,2) subsets we will get P(2,2) ordered sets of size 2, so the total number of ordered sets of size 2 is the product C(4,2)P(2,2). But, we already know that the answer is P(4,2), so we must have P(4,2) = C(4,2) P(2,2). Writing this in terms of numbers, we have 12 = 4(3) = C(4,2) 2! = 2 C(4,2). So, solving for C(4,2), we get 12/2 = 6. Doing the same thing in general gives us, P(n,k) = C(n,k) P(k,k). So, we can solve for C(n,k) and get:

This formula is sometimes written a little differently, by multiplying the top and bottom of the fraction by (n-k)! and using the fact that n(n-1)...(n-k+1) (n-k)! = n!, we can write:

Question: Find C(5,3), C(10,2), C(12,3) and C(6,4) by using this formula.


Answers:

6! = 6(5)(4)(3)(2)(1) = 720
7! = 7(6)(5)(4)(3)(2)(1) = 5040
8! = 8(7)(6)(5)(4)(3)(2)(1) = 40320
Notice how quickly these numbers get big . What is the biggest factorial number your calculator can handle?

P(5,2) = 5(4) = 20
P(7,4) = 7(6)(5)(4) = 840
P(6,1) = 6
P(3,3) = 3(2)(1) = 6
P(4,3) = 4(3)(2) = 24
C(5,3) = 5(4)(3)/3(2)(1) = 10
C(10,2) = 10(9)/2(1) = 45
C(12,3) = 12(11)(10)/3(2)(1) = 220
C(6,4) = 6(5)(4)(3)/4(3)(2)(1) = 15

You should check these with the results from Pascal's Triangle.