Back to the on-screen lesson ·
The numbers that count subsets by size, the one-sentence proofs of the rule, the symmetry and the row sums, and why the same numbers are the coefficients of an expansion.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to build a row of Pascal's triangle from the one above, compute a single binomial coefficient from the product form rather than from factorials, and use the symmetry to halve the work. You will also be able to prove an identity combinatorially — say what each side counts, then sort one set two ways or match two sets by a bijection — and explain why the coefficients of a binomial expansion are the same numbers that count subsets.
Lesson 17 defined $\binom{n}{k}$ as the ordered count divided by $k!$, and lesson 12 counted all the subsets of a set at once. This lesson puts the two together: the binomial coefficients are the subset count sorted by size, and almost every fact about them is proved by describing a set two ways.
$\binom{n}{k}$ is the number of $k$-element subsets of an $n$-element set. Pascal's triangle is the array whose $n$th row is $\binom{n}{0}$ to $\binom{n}{n}$. Pascal's rule is $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. The binomial theorem is the expansion of $(x + a)^n$, whose coefficients are exactly these numbers.
| $n$ | the row | adds to |
|---|---|---|
| $0$ | $1$ | $1$ |
| $1$ | $1\ \ 1$ | $2$ |
| $2$ | $1\ \ 2\ \ 1$ | $4$ |
| $3$ | $1\ \ 3\ \ 3\ \ 1$ | $8$ |
| $4$ | $1\ \ 4\ \ 6\ \ 4\ \ 1$ | $16$ |
Pascal's rule, $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$, is proved in one sentence. Fix one element of the set. Every $k$-subset either contains it — and then the remaining $k-1$ elements form a subset of the other $n-1$ — or does not, and is a $k$-subset of the other $n-1$. Two disjoint kinds, so the sum rule applies. No algebra anywhere.
Symmetry, $\binom{n}{k} = \binom{n}{n-k}$: send each subset to its complement. The map undoes itself, so it is a bijection, so the two counts agree. Choosing who is in is choosing who is out.
The row sum, $\sum_k \binom{n}{k} = 2^n$: the row counts the subsets sorted by size, and $2^n$ counts them all at once. One set, two counts.
All three proofs have the same shape, and it is the shape worth taking away. Say what each side counts; then either sort the same set two ways, or match the two sets by a bijection. The algebraic proofs exist and are longer and explain nothing.
The binomial theorem is the same idea applied to an expansion. $(x+a)^n$ is $n$ brackets multiplied out, and every term of the product chooses either $x$ or $a$ from each bracket. The terms with $k$ copies of $a$ number $\binom{n}{k}$, so $(x + a)^n = \sum_k \binom{n}{k} a^k x^{n-k}$. The coefficients are a count, which is why they are the triangle.
Another way: steps
To prove an identity about binomial coefficients:
Another way: picture
The triangle with a cell circled and the two cells above it shaded. The circled number is the sum of the shaded pair, and the picture is a proof once you know what the numbers count: the two shaded cells are the subsets that do and do not contain a fixed element.
$\binom{52}{5} = 52!/(5!\,47!)$ is correct and unusable. The product form is what to compute with:
$$\binom{n}{k} = \frac{n(n-1)\cdots(n-k+1)}{k!}$$
$\binom{52}{5} = (52 \cdot 51 \cdot 50 \cdot 49 \cdot 48)/120$ — five multiplications and a division, and the division always comes out whole, because the numerator counts ordered selections and every unordered one appears $k!$ times.
And use the symmetry before computing: $\binom{20}{17} = \binom{20}{3} = 1140$, three multiplications instead of seventeen. Choosing the smaller of $k$ and $n-k$ is free and always worth doing.
Adding the two entries diagonally instead of directly above. Pascal's rule combines $\binom{n-1}{k-1}$ and $\binom{n-1}{k}$, which sit immediately above and above-left in the usual drawing.
Reading $\binom{n}{k}$ as a fraction. It is a whole number, always, and a computation that does not come out whole has gone wrong.
Forgetting $\binom{n}{0} = 1$. There is exactly one subset with nothing in it, and the empty product convention $0! = 1$ is chosen to make the formula agree with that.
Proving an identity by checking rows. Two rows agreeing is evidence. The proof is the bijection.
Pascal's rule looks like an observation about an array of numbers, and it is a theorem with a one-sentence proof about subsets. That matters because the observation would give you no reason to believe the rule continues, and the proof gives a complete one. The same goes for the symmetry and the row sums: each is a statement about sets that happens to be visible in the array, and reading them off the array is how you find them, not how you know them.
How many $3$-subsets has $\{1, 2, 3, 4, 5\}$? Fix the element $5$ and sort the subsets by whether they contain it.
Sort, do not compute.
Those containing $5$: the other two elements form a $2$-subset of $\{1,2,3,4\}$, and there are $\binom{4}{2} = 6$. Those not: a $3$-subset of $\{1,2,3,4\}$, and there are $\binom{4}{3} = 4$.
Two disjoint kinds, counted separately.
Every $3$-subset is of exactly one kind, so $\binom{5}{3} = 6 + 4 = 10$ — which is Pascal's rule, and the argument used the sum rule and nothing else.
Exhaustive and disjoint: that is the whole check.
$(x + a)^3$ is three brackets multiplied out. Each term of the expansion picks $x$ or $a$ from each bracket.
Say what one term of the product is.
The terms with exactly one $a$ are the ones that picked $a$ from one bracket and $x$ from the other two, and there are $\binom{3}{1} = 3$ ways to choose which bracket.
The coefficient is a count of choices.
So $(x+a)^3 = x^3 + 3ax^2 + 3a^2x + a^3$, with coefficients $1, 3, 3, 1$ — row three. The triangle appears in algebra because the algebra was a counting problem.
The coefficients were never arbitrary.
Sorted by size, the odd sizes are $1$, $3$ and $5$, so the answer is $\binom{6}{1} + \binom{6}{3} + \binom{6}{5}$.
Sort by size and add the ones you want.
Row six is $1, 6, 15, 20, 15, 6, 1$, so that is $6 + 20 + 6 = 32$.
Read the entries off the row.
And $32 = 2^5 = 2^6/2$, which is lesson 16's transfer question answered again by a different route. Two counts of the same set agreeing is not a coincidence and is not a check — it is the proof, and finding the second count is usually easier than any algebra.
Fill in row $5$ of Pascal's triangle: the entries $\binom{5}{k}$ for $k = 0$ to $4$.
| $\binom{5}{k}$ | |
|---|---|
| $k = 0$ | 1 |
| $k = 1$ | |
| $k = 2$ | |
| $k = 3$ | |
| $k = 4$ |
What is $\binom{6}{3}$?
Answer:
Expand $(x + 6)^2$.
Answer:
What do all the entries of row $6$ of Pascal's triangle add up to?
Answer:
Build the combinatorial proof that $\binom{n}{k} = \binom{n}{n-k}$.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Fill in row $5$ of Pascal's triangle: the entries $\binom{5}{k}$ for $k = 0$ to $4$.
| $\binom{5}{k}$ | |
|---|---|
| $k = 0$ | 1 |
| $k = 1$ | |
| $k = 2$ | |
| $k = 3$ | |
| $k = 4$ |
You can build a row of the triangle, compute a coefficient without factorials, and prove an identity by counting. Say in your own words the one-sentence proof of Pascal's rule, and why a row adds to two-to-the-n. Next: the counting principle that guarantees a crowded box without ever saying which one.
10. Your turn: how many subsets of $\{1, \ldots, 6\}$ have an odd number of elements?, step 3