11.2: Binomial Coefficients
- Last updated
- Sep 29, 2021
- Save as PDF
- Page ID
- 86169
( \newcommand{\kernel}{\mathrm{null}\,}\)
Investigate!
In chess, a rook can move only in straight lines (not diagonally). Fill in each square of the chess board below with the number of different shortest paths the rook, in the upper left corner, can take to get to that square. For example, one square is already filled in. There are six different paths from the rook to the square: DDRR (down down right right), DRDR, DRRD, RDDR, RDRD and RRDD.
Here are some apparently different discrete objects we can count: subsets, bit strings, lattice paths, and binomial coefficients. We will give an example of each type of counting problem (and say what these things even are). As we will see, these counting problems are surprisingly similar.
Subsets
Subsets should be familiar, otherwise read over Section 0.3 again. Suppose we look at the set
First, a simpler question: How many subsets of
Of those 32 subsets, how many have 3 elements? This is not obvious. Note that we cannot just use the multiplicative principle. Maybe we want to say we have 2 choices (yes/no) for the first element, 2 choices for the second, 2 choices for the third, and then only 1 choice for the other two. But what if we said “no” to one of the first three elements? Then we would have two choices for the 4th element. What a mess!
Another (bad) idea: we need to pick three elements to be in our subset. There are 5 elements to choose from. So there are 5 choices for the first element, and for each of those 4 choices for the second, and then 3 for the third (last) element. The multiplicative principle would say then that there are a total of
Is this right? Well, we could list out all 10 of them, being very systematic in doing so, to make sure we don't miss any or list any twice. Or we could try to count how many subsets of
So far we have counted 12 of the 32 subsets. We have not yet counted the subsets with cardinality 2 and with cardinality 3. There are a total of 20 subsets left to split up between these two groups. But the number of each must be the same! If we say “yes” to exactly two elements, that can be accomplished in exactly the same number of ways as the number of ways we can say “no” to exactly two elements. So the number of 2-element subsets is equal to the number of 3-element subsets. Together there are 20 of these subsets, so 10 each.
Number of elements: | 0 | 1 | 2 | 3 | 4 | 5 |
Number of subsets: | 1 | 5 | 10 | 10 | 5 | 1 |
Bit Strings
“Bit” is short for “binary digit,” so a bit string is a string of binary digits. The binary digits are simply the numbers 0 and 1. All of the following are bit strings:
The number of bits (0's or 1's) in the string is the length of the string; the strings above have lengths 4, 1, 4, and 10 respectively. We also can ask how many of the bits are 1's. The number of 1's in a bit string is the weight of the string; the weights of the above strings are 2, 0, 4, and 5 respectively.
Definition: Bit Strings
- An
-bit string is a bit string of length . That is, it is a string containing symbols, each of which is a bit, either 0 or 1. - The weight of a bit string is the number of 1's in it.
is the set of all -bit strings. is the set of all -bit strings of weight .
For example, the elements of the set
The counting questions: How many bit strings have length 5? How many of those have weight 3? In other words, we are asking for the cardinalities
To find the number of 5-bit strings is straight forward. We have 5 bits, and each can either be a 0 or a 1. So there are 2 choices for the first bit, 2 choices for the second, and so on. By the multiplicative principle, there are
Finding the number of 5-bit strings of weight 3 is harder. Think about how such a string could start. The first bit must be either a 0 or a 1. In the first case (the string starts with a 0), we must then decide on four more bits. To have a total of three 1's, among those four remaining bits there must be three 1's. To count all of these strings, we must include all 4-bit strings of weight 3. In the second case (the string starts with a 1), we still have four bits to choose, but now only two of them can be 1's, so we should look at all the 4-bit strings of weight 2. So the strings in
This is an example of a recurrence relation. We represented one instance of our counting problem in terms of two simpler instances of the problem. If only we knew the cardinalities of
We can keep going down, but this should be good enough. Both
But wait —32 and 10 were the answers to the counting questions about subsets. Coincidence? Not at all. Each bit string can be thought of as a code for a subset. For the set
For example, the bit string
Now for a subset to contain exactly three elements, the corresponding bit string must contain exactly three 1's. In other words, the weight must be 3. Thus counting the number of 3-element subsets of
Lattice Paths
The integer lattice is the set of all points in the Cartesian plane for which both the
A lattice path is one of the shortest possible paths connecting two points on the lattice, moving only horizontally and vertically. For example, here are three possible lattice paths from the points
Notice to ensure the path is the shortest possible, each move must be either to the right or up. Additionally, in this case, note that no matter what path we take, we must make three steps right and two steps up. No matter what order we make these steps, there will always be 5 steps. Thus each path has length 5.
The counting question: how many lattice paths are there between
Notice that each of these strings must contain 5 symbols. Exactly 3 of them must be R's (since our destination is 3 units to the right). This seems awfully familiar. In fact, what if we used
The correspondence between bit strings and lattice paths does not stop there. Here is another way to count lattice paths. Consider the lattice shown below:
Any lattice path from (0,0) to (3,2) must pass through exactly one of
Binomial Coefficients
Binomial coefficients are the coefficients in the expanded version of a binomial, such as
In fact, there is a quicker way to expand the above binomials. For example, consider the next one,
If that looks daunting, go back to the case of
Similarly, in the expansion of
We still need the coefficients of
These numbers we keep seeing over and over again. They are the number of subsets of a particular size, the number of bit strings of a particular weight, the number of lattice paths, and the coefficients of these binomial products. We will call them binomial coefficients. We even have a special symbol for them:
Definition: Binomial Coefficients
For each integer
read “
the number of -bit strings of weight . is the number of subsets of a set of size each with cardinality . is the number of lattice paths of length containing steps to the right. is the coefficient of in the expansion of . is the number of ways to select objects from a total of objects.
The last bullet point is usually taken as the definition of
- How many subsets of
contain exactly 3 elements? We must choose of the 5 elements to be in our subset. There are ways to do this, so there are such subsets. - How many bit strings have length 5 and weight 3? We must choose
of the 5 bits to be 1's. There are ways to do this, so there are such bit strings. - How many lattice paths are there from (0,0) to (3,2)? We must choose 3 of the 5 steps to be towards the right. There are
ways to do this, so there are such lattice paths. - What is the coefficient of
in the expansion of We must choose 3 of the 5 copies of the binomial to contribute an . There are ways to do this, so the coefficient is .
It should be clear that in each case above, we have the right answer. All we had to do is phrase the question correctly and it became obvious that
Remember, this is because we can start the bit string with either a 1 or a 0. In both cases, we have
Since
Recurrence relation for
Pascal's Triangle
Let's arrange the binomial coefficients
This can continue as far down as we like. The recurrence relation for
We can use Pascal's triangle to calculate binomial coefficients. For example, using the triangle below, we can find