Start with a single 1 and make every entry the sum of the two above it. The rows that come out are the coefficients of (a + b)ⁿ, and each entry counts something exact: the number of ways to choose k things from n. This lesson builds the triangle and establishes what its entries count; the formula for computing one without building the rows above it comes next.
Core ideas
One construction, one counting interpretation, and one indexing convention that is where most of the errors start.
The apex is row 0, and the leftmost entry of any row is position 0. So row n has n + 1 entries, and the third number in row 6 is C(6,2) = 15 rather than C(6,3). The convention is arbitrary, but it is universal and it matches the exponents in (a + b)ⁿ.
An entry counts the ways of choosing k objects out of n. Single out one object: either it is chosen, and the remaining k - 1 come from the other n - 1, or it is not, and all k do. Those two cases are separate and cover everything, so the counts add — which is the sum-of-the-two-above rule.
C(n,k) = C(n,n-k), because naming the k objects to take is the same act as naming the n - k to leave. Row 8 is written once you know 1, 8, 28, 56, 70: the rest is 56, 28, 8, 1, the first four of those read backwards, with the central 70 written once.
The material
The construction rule, the counting problem the entries answer, and the patterns worth trusting.
The array of numbers whose row 0 is a single 1, in which every row begins and ends with 1, and in which every other entry is the sum of the two entries immediately above it. Rows are numbered from 0 downwards and positions within a row from 0 from the left.
The name is a historical accident: the array appears in Chinese, Indian and Persian mathematics centuries before Pascal, who wrote a treatise on it in the 1650s.
Write C(n,k) for the entry in row n at position k. In this lesson that is all the symbol means — a name for a number read off the array — and the building rule is C(n,k) = C(n-1,k-1) + C(n-1,k) for 0 < k < n, with C(n,0) = C(n,n) = 1. “The Binomial Theorem” gives a formula in factorials that produces C(n,k) directly, without the rows above it.
Here is a question with nothing to do with triangles. A group of three people, A, B and C, must send a delegation. How many different delegations are there of each size?
The number of ways to choose k objects from a set of n distinct objects is C(n,k), the entry in row n at position k.
Let N(n,k) be the number of ways to choose k from n. There is one way to choose none and one way to choose all, so N(n,0) = N(n,n) = 1, matching the edges of the triangle.
Now fix one particular object. The selections that include it are completed by choosing k - 1 from the other n - 1, and there are N(n-1,k-1) of those. The selections that exclude it are choices of k from the other n - 1, and there are N(n-1,k). No selection is in both groups and none is outside them, so N(n,k) = N(n-1,k-1) + N(n-1,k).
So N starts as the triangle does and grows by the same rule, which forces the two tables to agree row by row. Stating that last step properly is what mathematical induction is for, and the Discrete Mathematics path does it; the two rules and the two starting rows are what this course checks.
□
There is a second count in the same picture. Start at the apex and walk down, going left or right at each step. The number of routes that reach a given entry is that entry, because every route arrives from one of the two entries above it. A route of n steps that lands at position k went right k times, so the routes are another way of choosing which k of the n steps go right.
Row n adds up to 2ⁿ. The reason is the delegation table above: sorting all the subsets of an n-element set by size counts each subset exactly once, and a set of n things has 2ⁿ subsets, one for each way of saying yes or no to each thing. Row 6 gives 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64, and 2⁶ = 64.
With alternating signs the same rows give 0, for every n ≥ 1. Row 4 gives 1 - 4 + 6 - 4 + 1 = 0 and row 7 gives 1 - 7 + 21 - 35 + 35 - 21 + 7 - 1 = 0. For odd n the symmetry pairs each entry with an equal one of the opposite sign, which settles that case; for even n the cancellation is real but the clean reason for it is the binomial theorem with a = 1 and b = -1, which is the subject of “The Binomial Theorem”.
The entries grow quickly: C(20,10) = 184756, and reaching it by addition means building twenty rows, one hundred and ninety additions. That is the argument for a formula, and it is what “The Binomial Theorem” supplies.
Interactive
Every entry by addition and by C(n, k), and every row sum against 2^n
Method
Four steps, and the last one costs one line of addition and is worth doing every time.
Write the index above each entry before reading anything off. For C(8,3) you want row 8, and the fourth number along it, because position 3 follows positions 0, 1, 2.
Each new row starts and ends with 1; every entry between them is the sum of the pair above. Take the row you trust, not the row you half remember.
C(n,k) = C(n,n-k), so the second half of a row is the first half reversed. In an odd-numbered row the two central entries are equal; in an even-numbered row there is a single central entry.
Add the entries. A row that does not total 2ⁿ contains an error. A row that does may still contain two errors that cancel, so the symmetry is worth a second look.
Three rows built by addition from row 5, each checked by adding it up and comparing with the power of two it should be.
Each row was produced one way and checked another, which is what the 2ⁿ line is for. It establishes that the entries of that row total the right amount; it does not establish that every entry is right, since two compensating errors would pass. Reading the row backwards and finding the same numbers is a second, independent check.
56 answers a question about people with no obvious triangle in it. The connection is the argument above: the delegations of size 3 from 8 either include a particular person or do not, which is the same split that built the row.
For a faded row construction, start from the completed row 8 above and build row 9. The supplied edge entries are the two 1s; every interior entry is still yours. Use symmetry to check the row, add it to compare with 2⁹, and read C(9,4) as a sentence about choosing four people from nine before opening the quiz.
You should be able to produce row 8 from row 5 without error, read C(8,3) off it with the positions counted correctly, and say why the entry is the answer to a question about choosing delegations. The 2ⁿ check should be automatic.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.