Section2.1Pascal's Triangle and Binomial Coefficients
¶Let's start our investigation of combinatorics by examining Pascal's Triangle. If you are already familiar with this mathematical object, try to see it with fresh eyes. Look at the triangle as if you have no idea where it comes from. What do you notice?
Activity63
Treating Pascal's Triangle as nothing more than a triangular array of numbers, what do you notice about it? Are there any patterns to the numbers? Try to find some patterns and then see if you can answer (or have already answered) the following:
(a)
How are the entries in the triangle found? What would the next row down be?
(b)
What is the sum of the entries in the \(n\)th row?
(c)
What is \(1 - 5 + 10 - 10 + 5 - 1\text{?}\) What pattern is this an example of, and does it always work?
(d)
What is \(1 + 3 + 6 + 10 + 15\text{?}\) What pattern is this an example of, and does it always work?
(e)
What is \(1+ 7 + 15 + 10 + 1\text{?}\) What pattern is this an example of, and does it always work?
(f)
Are there any groups of numbers in the triangle that are particularly recognizable?
We would like to understand why the patterns you discovered above exist, and to prove that they really do exist everywhere in the triangle. There are at least two ways we can proceed (and we will try to proceed in both ways to maximize our understanding). First, we can use notation to describe the entries in the triangle, provide a definition for what each entry is, and prove our results entirely based on these definitions. Second, we can ascribe some meaning to the entries in the triangle, saying what the numbers represent, and then make arguments about those representations.
The advantage to pursuing both these approaches is that doing so creates a feedback loop. A fact we establish using pure symbolic manipulation allows us to conclude something about the real world and what these numbers represent. That helps us understand the applications better, which in turn might help us make arguments about those applications, which can then establish a purely symbolic fact about the triangle.
Let's pause and just for fun consider a few discrete math questions that probably have nothing to do with Pascal's Triangle or each other. Probably.
Activity64
The integer lattice is the set of all points in the Cartesian plane for which both the \(x\) and \(y\) coordinates are integers.
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 \((0,0)\) to \((3,2)\text{:}\)
(a)
How many lattice paths are there between \((0,0)\) and \((3,1)\text{?}\) Draw or list them all (you might want to invent some notation for describing a path without drawing it).
(b)
How many lattice paths are there between \((0,0)\) and \((2,2)\text{?}\) Draw or list them all to be sure.
(c)
How many lattice paths are there between \((0,0)\) and \((3,2)\text{?}\) How can you be sure?
Activity65
Recall that a subset \(A\) of a set \(B\) is a set all of whose elements are also elements of \(B\text{;}\) we write \(A \subseteq B\text{.}\) For example, some of the subsets of \(B = \{1,2,3,4,5\}\) are \(\{2,4,5\}\text{,}\) \(\{1,2,3,4,5\}\) and \(\emptyset\text{.}\) Recall also that the cardinality of a set is simply the number of elements in it.
Since we will often consider sets of the form \(\{1,2,3,\ldots,n\}\text{,}\) let's adopt the notation \([n]\) for this set.
(a)
Write out all subsets of \([3] = \{1,2,3\}\text{.}\) Then group the subsets by cardinality. How many subsets have cardinality 0? How many have cardinality 1? 2? 3?
(b)
Write out all subsets of \([4]\text{,}\) and determine how many have each possible cardinality.
(c)
How many subsets of \([5]\) are there of each cardinality? Try to answer this questions without writing out all 32 subsets.
Activity66
Some definitions: A bit is either 0 or 1 (bit is short for “binary digit”). Thus a bit string is a string of bits. The length of a bit string is the number of bits in the string; the weight of a bit string is the number of 1's in the string (or equivalently, the sum of the bits). A \(n\)-bit string means a bit string of length \(n\text{.}\)
We will write \(\B^n_k\) to mean the set of all \(n\)-bit strings of weight \(k\text{.}\) So for example, some of the elements in \(\B^5_3\) are,
\begin{equation*}
11100 \qquad 10101 \qquad 01101.
\end{equation*}
(a)
Write out all \(3\)-bit strings. Group these by weight. How many strings are there of each weight?
(b)
Write out all \(4\)-bit strings. You might want to use the list you had in the previous part as a starting point (how would you do this?). Again, group these strings by weight and see how many there are of each type.
(c)
How many \(5\)-bit strings of weight 3 are there? List all of these, and say how they relate to some of the \(4\)-bit strings you found above.
We are not quite ready to consider the algebraic approach yet, but here is a fun algebra exercise.
Activity67
Multiply out (and collect like terms): \((x+y)^3\text{.}\) Repeat for \((x+y)^4\) and \((x+y)^5\text{.}\)
(a)
What is the coefficient of \(x^3y^2\) in the expansion of \((x+y)^5\text{?}\)
(b)
What are the coefficients of \(x^2y^2\) and \(x^3y\) in the expansion of \((x+y)^4\text{?}\) How does this relate to the previous question? Why does this make sense?
(c)
If you believe the connection between coefficients and Pascal's triangle you have discovered above, find the coefficient of \(x^7y^4\) in the expansion of \((x+y)^{11}\) using Pascal's triangle.
Hopefully by now you have some questions that are begging to be answered. Here are two that we will focus on specifically:
Why are the answers to all the counting questions above the same as each other?
Why are the answers to all the counting questions above numbers in Pascal's triangle?
We could answer the first question by answering the second: if we can say why each answer is a particular entry in Pascal's triangle, then we know two answers will be equal because they are in the same place on the triangle. But we can do better. In fact, we should be able to explain why these counting questions correspond to each other without knowing any of the answers.
Activity68
(a)
Explain why the number of lattice paths from \((0,0)\) to \((k,n-k)\) is the same as number of \(n\)-bit strings of weight \(k\text{.}\) You do not need to give a formal proof here, just explain the idea.
(b)
Explain why the number of \(n\)-bit strings of weight \(k\) is the same as the number of \(k\)-element subsets of \([n] = \{1,2,3,\ldots, n\}\text{.}\) Again, an informal argument is fine.
(c)
Explain why the number of \(k\)-element subsets of \([n]\) is the same as the coefficient of \(x^ky^{n-k}\) in the expansion of \((x+y)^n\text{.}\)
HintThis is a little harder. It might help to notice that there is really nothing special about \([n]\) except that it contains \(n\) elements. In fact, what can you say about the number of \(k\)-element subsets of any \(n\)-element set? Then, what \(n\)-element set would we look at when expanding \((x+y)^n\text{?}\)
Are you satisfied with the explanations you gave above? Do you think they would count as a formal mathematical proof that the counting questions have the same answer? One way to make this sort of an argument more precise is to involve precisely defined mathematical objects.
Activity69
Consider functions \(f:X \to Y\) where \(X\) and \(Y\) are finite sets. In fact, let's say \(X = [4]\text{.}\) If you need a refresher on basic ideas about functions, check out Section B.3.
(a)
Can you say anything at all about \(Y\) if you know there is some function \(f:X \to Y\text{?}\) Give some examples of sets \(Y\) and functions \(f\text{.}\)
(b)
What if \(f:X \to Y\) is injective (in other words, one-to-one)? Which of the examples you found above no longer work? What can you conclude about \(Y\text{?}\)
(c)
What if \(f:X \to Y\) is surjective (i.e., onto)? Now what can you say about \(Y\text{?}\)
(d)
What if \(f:X\to Y\) is bijective (so both injective and surjective)? State the general principle.
The previous activity was meant to help you discover what is usually called the bijection principle: Two sets \(X\) and \(Y\) have the same cardinality if and only if there is a bijection \(f:X \to Y\).
If you want to prove that two sets have the same number of elements, all that is requires is to define a function from one set to the other, and prove that the function is a bijection. For us, those two sets will be the set of outcomes we are counting. So for example, we can show that the set of \(n\)-bit strings of weight \(k\) has the same cardinality as the set of \(k\)-element subsets of \([n]\text{.}\) This will prove that the counting questions, “how many \(n\)-bit strings of weight \(k\) are there?” and, “how many \(k\)-element subsets of \([n]\) are there?” have the same answer.
Activity70
(a)
Define a bijection \(f:X \to Y\) where \(X\) is the set of lattice paths from \((0,0)\) to \((k,n-k)\) and \(Y\) is the set of \(n\)-bit strings of weight \(k\text{.}\) Prove that \(f\) really is a bijection.
(b)
Define a bijection \(f:X \to Y\) where \(X\) is the set of \(n\)-bit strings of weight \(k\) and \(Y\) is set of \(k\)-element subsets of \([n] = \{1,2,3,\ldots, n\}\text{.}\) Again, prove that \(f\) is a bijection.
(c)
Can you now conclude that the number of lattice paths from \((0,0)\) to \((k,n-k)\) is the same as the number of \(k\)-element subsets of \([n]\text{?}\) Can you easily give the bijection (and be sure it is one)?
So all these counting questions correspond to each other. Why do the answers always fall in Pascal's triangle? To answer this, we need to start with a definition for the numbers in Pascal's triangle.
First, some notation: let's write \(\binom{n}{k}\) for the \(k\)th entry in row \(n\text{.}\) For both \(n\) and \(k\text{,}\) start counting at 0. So for example \(\binom{5}{1} = 5\text{,}\) and \(\binom{n}{0} = \binom{n}{n} = 1\) for all \(n\) (or at least the ones we can see). We will read \(\binom{n}{k}\) as “\(n\) choose \(k\)” for reasons that will become clear soon.
Now we need to decide what \(\binom{n}{k}\) should be defined as. It is not enough to simply define it as the specific entry in Pascal's triangle, since we haven't yet defined Pascal's triangle (we will want to define Pascal's triangle as the triangle of the numbers \(\binom{n}{k}\)). Here are some choices:
Possible Definitions for \(\binom{n}{k}\)
For each integer \(n \ge 0\) and integer \(k\) with \(0 \le k \le n\) the number
\begin{equation*}
{n\choose k},
\end{equation*}
read “\(n\) choose \(k\)” is:
- the number of \(n\)-bit strings of weight \(k\text{,}\) that is, \({n\choose k} = |\B^n_k|\text{.}\)
- \({n \choose k}\) is the number of subsets of a set of size \(n\) each with cardinality \(k\text{.}\)
- \({n \choose k}\) is the number of lattice paths of length \(n\) containing \(k\) steps to the right.
- \({n \choose k}\) is the coefficient of \(x^ky^{n-k}\) in the expansion of \((x+y)^n\text{.}\)
- \({n \choose k}\) is the number of ways to select \(k\) objects from a total of \(n\) objects.
\(\binom{n}{0} = \binom{n}{n} = 1\) and for all \(n \ge 1\) and \(1 \lt k \lt n\) we have \(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\text{.}\)
You have already prove that choices 1, 2 and 3 are equivalent, and we have good reason to believe these are also equivalent to choice 4.
What about choice 5? This is new, although not really, as it captures all of the previous four: Each of our counting problems above can be viewed in this way:
How many bit strings have length 5 and weight 3? We must choose \(3\) of the 5 bits to be 1's. There are \({5 \choose 3}\) ways to do this, so there are \({5 \choose 3}\) such bit strings.
How many subsets of \(\{1,2,3,4,5\}\) contain exactly 3 elements? We must choose \(3\) of the 5 elements to be in our subset. There are \({5 \choose 3}\) ways to do this, so there are \({5 \choose 3}\) such subsets.
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 \({5 \choose 3}\) ways to do this, so there are \({5 \choose 3}\) such lattice paths.
What is the coefficient of \(x^3y^2\) in the expansion of \((x+y)^5\text{?}\) We must choose 3 of the 5 copies of the binomial to contribute an \(x\text{.}\) There are \({5 \choose 3}\) ways to do this, so the coefficient is \({5 \choose 3}\text{.}\)
In fact, choice 5 is usually taken as the definition of \(\binom{n}{k}\text{,}\) which is why we say \(n\) choose \(k\text{.}\) Although interestingly enough, the other common name for \(\binom{n}{k}\) is a binomial coefficient, which refers to the coefficients of the binomial \((x+y)^n\text{.}\)
What does all this have to do with Pascal's triangle though? If you are like me, you think of the entries in the triangle as the result of adding the two entries above it. That is, Pascal's triangle contains those numbers described by choice 6 above.
Recurrence relation for \({n \choose k}\)
For any \(n \ge 1\) and \(0 \lt k \lt n\text{:}\)
\begin{equation*}
{n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}.
\end{equation*}
The last piece of the puzzle is to connect this definition to all the others. Of course given the work done above, it would be enough to prove that any one of the models for binomial coefficients match the recurrence for Pascal's triangle, but it is instructive to check all four.
Activity71
(a)
Prove that bit strings satisfy the same recurrence as Pascal's triangle. That is prove that \(|\B^n_k| = |\B^{n-1}_{k-1}| + |\B^{n-1}_k|\text{.}\)
(b)
Prove that subsets satisfy the same recurrence as Pascal's triangle. Make sure you clearly state what you are proving.
(c)
Prove that lattice paths satisfy the same recurrence as Pascal's triangle. What exactly do you need to prove here?
(d)
Prove that binomial coefficients (the actual coefficients of the expansion of the binomial \((x+y)^n\)) satisfy the same recurrence as Pascal's triangle.
At last we can rest easy that can use Pascal's triangle to calculate binomial coefficients and as such find numeric values for the answers to counting questions. How many pizza's containing three distinct toppings can you make if the pizza place offers 10 toppings? Well the answer should be \(\binom{10}{3}\text{,}\) and Pascal's triangle says that is 120.
