Basic Problemscountingcombinatoricsgrid

Binomial Coefficient

Given integers n and r, compute the number of ways to choose r items out of a set of n distinct items, without regard to the order the items are chosen in.

Do this lesson first: climbing stairs

Example input

n = 6, r = 3, so the question is C(6, 3)

Expected output

20

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[n][r] is the number of ways to choose r items out of n distinct items, order ignored, so the cell holds a COUNT and nothing about which items were picked. Two counts name the state, how many there are to choose from and how many to choose, so the table is a grid even though there is no input array anywhere on this page. Set this next to min-sum-in-a-triangle, which fills a table with the same lower-triangular shape: there, every cell has a number of its own out of a given triangle, so the input contributes a term at every single cell. Here there is no input at all to read. A cell is fully described by the pair of counts labelling it, and its value comes from cells alone.

dp[n][r] = dp[n - 1][r - 1] + dp[n - 1][r]

Single out one particular item, say the last of the n, and ask whether a selection contains it. If it does, the remaining r - 1 picks come from the other n - 1 items, and there are dp[n - 1][r - 1] ways to make them. If it does not, all r picks come from the other n - 1 items, and there are dp[n - 1][r] ways. Every selection of r items falls into exactly one of those two groups, because it either holds that item or it does not, so the groups are disjoint and together exhaustive and the two counts simply add. It is a SUM rather than a min or a max because this is a counting problem: both cases really happen, across different selections, and we want the total of them, not the better of them. That is the same distinction as count-all-paths-in-a-grid adding where min-cost-path takes a min.

BOTH outer edges are given, and the reason is arithmetic rather than convention. dp[n][0] = 1 for every row: there is exactly one way to choose nothing, the empty selection, and it always exists. It has to be a base because the cell the recurrence would send it to is dp[n - 1][-1], column -1, which is off the table altogether. dp[n][n] = 1 for every row: there is exactly one way to choose all n items, take every one of them. It has to be a base because the cell the recurrence would send it to is dp[n - 1][n], which sits above the diagonal and does not exist. Every cell with 1 <= r <= n - 1 is computed, and each of those has exactly two live predecessors, never one. THE DOTS ARE NOT ZEROS, in the sense that nothing is ever written to them and no cell ever reads one: a grid has to be a rectangle, so the table is declared n + 1 by n + 1, but only the cells with column <= row belong to the triangle, and a position with column > row would be asking for more items than the row has to offer. Here that matters less than it does in min-sum-in-a-triangle, and the difference is worth being precise about rather than borrowing that page's alarm. There, a zero above the diagonal would be a free number a descent could cheat through, and the answer would come out below the truth. The two pages depend on the same two directions, up-and-to-the-left and straight up, so that is not the difference. The difference is that this page makes the DIAGONAL a base while the triangle computes it: a computed cell here reads dp[n - 1][r - 1] and dp[n - 1][r], and since r <= n - 1 both of those are on or below the diagonal, so the empty half is unreachable from any live cell. Zero is even the mathematically correct value for those positions, since there are no ways to choose more items than exist. The triangle has no such guarantee, because its diagonal cells are computed rather than given, and the straight-up read from one of those lands in the row above, which is a column shorter; that is the read its spec has to leave out by hand. They are dots because they are not part of the question, not because a zero there would corrupt anything. Filling row-major, left to right within each row, means both cells a computed cell reads are final before it reads them, which is the only ordering property the recurrence needs.

Tabulation, one row-major sweep, and the case for the table here is NOT the usual one, so it is worth stating plainly which case is being made. C(n, 3) has a closed form that runs in two multiplications and one division, n(n - 1)(n - 2) / 6, and a closed form of some shape is what the independent check behind this page computes; it uses the multiplicative form rather than this one, interleaving its divisions so no partial product ever leaves the integers. So nothing on this page is being rescued from an exponential cost by the table, and any page that tells you otherwise about this particular problem is wrong. Two other arguments are the real ones. EXACTNESS: the additive form never leaves the integers, because every cell is the sum of two whole numbers already in the table, so there is no division and no rounding anywhere in the sweep. Reach for n! / (r! (n - r)!) instead and it breaks long before the answers get large: 19! is already past the largest integer a double holds exactly, and in JavaScript that route returns 253.00000000000003 for C(23, 2), whose true value is the integer 253, and overflows the numerator to Infinity by C(171, 2), whose answer is only 14535. GENERALITY: the sweep fills C(n, r) for every pair of counts up to the bottom row rather than only the pair the slider highlights, so one pass answers every question of this shape at once, which is what makes this same table the right picture for reading out a whole row of Pascal's triangle. One caution on the exponential story, because it does get told wrong in both directions: writing THIS recurrence as a plain recursion with no table genuinely does blow up, since the call tree bottoms out in one leaf per selection and C(30, 15) makes over 150 million calls. That is a true fact about the recursion and a false one about the problem, which a closed form settles instantly. COST: the triangle up to row n holds (n + 1)(n + 2) / 2 cells, so the sweep is O(n^2) time and O(n^2) space; a cell only ever reads the row above it, so one rolling row is enough, and a sweep that only needs column r can stop there for O(n r). And unlike most pages in this course, memoization here does strictly LESS work than the sweep, which is worth admitting rather than glossing. min-sum-in-a-triangle says the opposite about its own table and is right to: its answer is a scan of the whole bottom row, so every cell of that triangle lies under the answer and there is nothing for memoization to skip. The answer here is ONE cell, so most of this table lies outside it. A memoized recursion from dp[n][3] only ever descends into cells with column 3 or less, so it fills 4n - 9 cells against the sweep's (n + 1)(n + 2) / 2, which is roughly O(n r) against O(n^2). That is 15 of this table's 28 live cells at n = 6 and 23 of 45 at n = 8. The surplus is not waste, though, and it is not an argument against the sweep either: the extra cells ARE the other answers, which is the GENERALITY point above. Across the slider's whole range the sweep costs under 2.15 times the memoized recursion, and the factor is not even monotone in n: it is 2.14 at the slider's minimum of 4, dips to its lowest of 1.87 at n = 6, and is back to 1.96 at 8. It does grow without bound eventually, since n^2 outruns 4n, but the slider does not reach far enough to show that: the factor at the maximum of 8 is still below its value at the minimum of 4. So the sweep is the right thing here for what the extra cells ARE, not because memoization would cost the same.

Time O(n^2) to fill the triangle up to row n, or O(n r) if the sweep stops at column rSpace O(n^2), reducible to O(r) with one rolling row

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

BOTH outer edges are given, and the reason is arithmetic rather than convention. dp[n][0] = 1 for every row: there is exactly one way to choose nothing, the empty selection, and it always exists. It has to be a base because the cell the recurrence would send it to is dp[n - 1][-1], column -1, which is off the table altogether. dp[n][n] = 1 for every row: there is exactly one way to choose all n items, take every one of them. It has to be a base because the cell the recurrence would send it to is dp[n - 1][n], which sits above the diagonal and does not exist. Every cell with 1 <= r <= n - 1 is computed, and each of those has exactly two live predecessors, never one. THE DOTS ARE NOT ZEROS, in the sense that nothing is ever written to them and no cell ever reads one: a grid has to be a rectangle, so the table is declared n + 1 by n + 1, but only the cells with column <= row belong to the triangle, and a position with column > row would be asking for more items than the row has to offer. Here that matters less than it does in min-sum-in-a-triangle, and the difference is worth being precise about rather than borrowing that page's alarm. There, a zero above the diagonal would be a free number a descent could cheat through, and the answer would come out below the truth. The two pages depend on the same two directions, up-and-to-the-left and straight up, so that is not the difference. The difference is that this page makes the DIAGONAL a base while the triangle computes it: a computed cell here reads dp[n - 1][r - 1] and dp[n - 1][r], and since r <= n - 1 both of those are on or below the diagonal, so the empty half is unreachable from any live cell. Zero is even the mathematically correct value for those positions, since there are no ways to choose more items than exist. The triangle has no such guarantee, because its diagonal cells are computed rather than given, and the straight-up read from one of those lands in the row above, which is a column shorter; that is the read its spec has to leave out by hand. They are dots because they are not part of the question, not because a zero there would corrupt anything. Filling row-major, left to right within each row, means both cells a computed cell reads are final before it reads them, which is the only ordering property the recurrence needs.

row n: how many items there are to choose from

0

1

2

3

4

5

6

0

1

·

1

·

2

1

2

1

·

3

1

3

1

·

4

1

4

6

4

1

·

5

1

5

10

5

1

·

6

1

6

15

20

15

6

1

column r: how many to choose, so the cell is C(n, r)

binomial-coefficient.ts

1function binomialCoefficient(n, r) {
2 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
3 for (let i = 0; i <= n; i++) {
4 dp[i][0] = 1;
5 dp[i][i] = 1;
6 for (let j = 1; j < i; j++) {
7 const takeIt = dp[i - 1][j - 1];
8 const leaveIt = dp[i - 1][j];
9 dp[i][j] = takeIt + leaveIt;
10 }
11 }
12 return dp[n][r];
13}

Base caseComputedBeing readAnswer

The code, the trap, the variations

binomial-coefficient.ts

1function binomialCoefficient(n, r) {
2 const dp = Array.from({ length: n + 1 }, () => new Array(n + 1).fill(0));
3 for (let i = 0; i <= n; i++) {
4 dp[i][0] = 1;
5 dp[i][i] = 1;
6 for (let j = 1; j < i; j++) {
7 const takeIt = dp[i - 1][j - 1];
8 const leaveIt = dp[i - 1][j];
9 dp[i][j] = takeIt + leaveIt;
10 }
11 }
12 return dp[n][r];
13}

Where people go wrong

Computing it as n! / (r! (n - r)!). The formula is correct on paper and wrong in a fixed-width number type, and it fails far earlier than anyone expects: 19! is already past the largest integer a double represents exactly, so in JavaScript that route hands back 253.00000000000003 for C(23, 2), whose true value is the small integer 253, and by C(171, 2) the numerator has overflowed to Infinity while the answer itself is only 14535. The additive table never divides and never leaves the integers, which is the whole reason to prefer it at these sizes. The second real mistake is reading the two axes the wrong way round: C(6, 3) is dp[6][3], the 20, while dp[3][6] is a dot, because choosing 6 items out of 3 is not a small number, it is not a thing at all. If a lookup lands above the diagonal, the arguments went in swapped.

Return C(n, r) modulo a prime p, the usual competitive-programming form.
The recurrence does not change at all: still the sum of the two cells above. Only the write changes, taking a % p after the addition, which keeps every cell below p and removes the overflow question entirely. Shape, bases, fill order and dependency arrows are all untouched, which is why this variation is a one-token edit rather than a redesign.
Ask for an entire row of the triangle rather than one entry.
Nothing about the recurrence, the bases or the fill order moves; only what you read at the end does, switching from one highlighted cell to the whole bottom row. That is the generality argument made concrete: the sweep was already computing every entry of that row, so the extra answers cost nothing. It is also the reason the O(n) rolling-row space trick survives here, since the final row is exactly what the rolling row holds.
Count partitions of n labelled items into exactly r non-empty unordered groups, the Stirling numbers of the second kind.
The two predecessors stay the same two cells above and the triangular shape stays identical, so the picture on this page is unchanged. What changes is that the second term picks up the column as a multiplier, dp[n][r] = dp[n - 1][r - 1] + r * dp[n - 1][r], because an item left out of the singled-out group can join any one of the r groups already there rather than just one. The diagonal is still 1, but the left edge flips to 0 for every row past the first: there is no way to split a non-empty set into zero groups. Same arrows, different arithmetic on them, and a much faster-growing table.

Ways to Partition a Set Pascal's Triangle