In how many ways can you choose 2 of 5 things? Call them A, B, C, D and E. The pairs are AB, AC, AD, AE, BC, BD, BE, CD, CE and DE: 10. The number of ways to choose r things from n, when the order does not matter, is written C(n, r), and read “n choose r”. So C(5, 2) = 10. These numbers are the binomial coefficients; Counting in the statistics course shows where they come from. This page is about computing them.
Building Pascal’s triangle
Each cell is the sum of the two above it
long long choose_rec(int n, int r){ calls++; if (r == 0 || r == n) return 1; long long a = choose_rec(n - 1, r - 1); long long b = choose_rec(n - 1, r); return a + b;} long long choose_row(int n, int r){ long long row[MAXN + 1]; row[0] = 1; for (int i = 1; i <= n; i++) { row[i] = 1; for (int j = i - 1; j > 0; j--) row[j] = row[j] + row[j - 1]; } return row[r];} int main(void){ long long c = choose_rec(5, 2); printf("recursive C(5, 2) = %lld in %ld calls\n", c, calls); long long d = choose_row(5, 2); printf("table C(5, 2) = %lld\n", d); return 0;}main calls choose_rec(5, 2).
- calls by choose_rec
- 0
- additions by choose_row
- 0
Output
Describe this picture
Lines 7 to 36 of choose.c, with the line about to run marked, beside a picture in two parts. At the top is a triangle of cells under the words “Row n, column r holds C(n, r)”: rows 0 to 5 down the side, columns 0 to 5 across the top, row n with n + 1 cells. Each cell shows a ”?” until it has a value. Under it is a tree of calls, “choose_rec(n, r): one circle per call”, with “n,r” in each circle and its value under it once it returns. The clip plays once, about 25 seconds. First choose_rec(5, 2) runs: each call adds a circle to the tree and lights its cell in the triangle, and when the call returns, its value appears under the circle and in the cell. The calls go down the left first, to C(1, 0) and C(1, 1), and the values 1, 2, 3, 4 come back up. Then C(4, 2) asks for C(3, 1) again, which asks for C(2, 1) again, and later C(3, 2) asks for C(2, 1) a third time. The words under the triangle say so (“C(2, 1) again: the third time”), the two circles of C(3, 1) are filled in one colour and the three of C(2, 1) in another, and the two cells take the same colours. The calls end at 19 with 10 in cell (5, 2). Then the triangle is cleared and choose_row builds it row by row from the top: each row starts and ends with 1, and each cell between is lit as it is made, with the two cells above it, while the words under the triangle give the sum, such as “C(4, 2) = C(3, 1) + C(3, 2) = 3 + 3”. Each row is filled from the right. The clip rests on the full triangle down to row 5: 1, 5, 10, 10, 5, 1. Under the picture are one sentence on the current step and two readouts: “calls by choose_rec”, which ends at 19, and “additions by choose_row”, which ends at 10. The output is two lines: recursive C(5, 2) = 10 in 19 calls and table C(5, 2) = 10. The transport plays and pauses, steps back or forward, and scrubs; a paused step is kept in the page address as pascal.step.
The rule
Take the n-th thing, E in the example. Every choice of r things either includes it or does not.
- If it is included, the other r − 1 come from the first n − 1 things: C(n − 1, r − 1) ways.
- If it is not, all r come from the first n − 1: C(n − 1, r) ways.
So
The base cases are the choices with only one way: C(n, 0) = 1 (choose nothing) and C(n, n) = 1 (choose everything). For the pairs of A to E: the pairs with E are AE, BE, CE and DE, which is C(4, 1) = 4, and the pairs without E are the 6 pairs of A to D, C(4, 2) = 6. 4 + 6 = 10.
Write the values in a triangle, row n holding C(n, 0) to C(n, n), and the rule says each cell is the sum of the two above it: the one directly above and the one above and to the left. This is Pascal’s triangle.
Key idea
C(n, r) = C(n − 1, r − 1) + C(n − 1, r), with C(n, 0) = C(n, n) = 1. Each row of Pascal’s triangle is built from the row above it.
The code and its cost
By recursion
The rule turns straight into a recursive function:
long long choose_rec(int n, int r)
{
calls++;
if (r == 0 || r == n)
return 1;
long long a = choose_rec(n - 1, r - 1);
long long b = choose_rec(n - 1, r);
return a + b;
}choose_rec(5, 2) makes 19 calls. There is a neat way to see why. Every value comes from adding up 1s returned by base cases, so to reach 10 there must be 10 calls that are base cases. Every other call adds two values into one, and it takes 9 such additions to join 10 values into 1. So 10 + 9 = 19 calls, and in general 2C(n, r) − 1.
The tree in the clip has the same problem as fib’s in Tree recursion (4.3): C(3, 1) is worked out twice and C(2, 1) three times, from scratch each time. For C(30, 15) = 155,117,520 the recursion would make 310,235,039 calls.
One row at a time
Instead, build the triangle from the top, as the second half of the clip does. A row needs only the row above it, so the program keeps a single array, row, and turns row i − 1 into row i in place:
long long choose_row(int n, int r)
{
long long row[MAXN + 1];
row[0] = 1;
for (int i = 1; i <= n; i++) {
row[i] = 1;
for (int j = i - 1; j > 0; j--)
row[j] = row[j] + row[j - 1];
}
return row[r];
}The picture keeps every row so that you can see the two cells above each sum; the program has only one row at any time. After each round of the outer loop it holds 1 1, then 1 2 1, 1 3 3 1, 1 4 6 4 1 and 1 5 10 10 5 1.
Why does the inner loop go from the right? Because row[j] needs the old values of row[j] and row[j − 1], both from the row above. Going right to left, row[j − 1] has not been changed yet when row[j] uses it. Going left to right, row[j − 1] would already hold its new value, and the sums would be wrong.
The costs
Row i takes i − 1 additions, so building down to row n takes 1 + 2 + … + (n − 1) = n(n − 1)/2 additions, about n²/2. For C(5, 2) that is 10, against the recursion’s 19 calls. The counts are close for such a small case, but for C(30, 15) the rows take 435 additions against 310,235,039 calls. The memory is one row of n + 1 cells.
Why not the formula?
There is also a formula, C(n, r) = n! / (r! (n − r)!). It looks like the quick way, but the factorials in it grow far faster than the answer. 20! = 2,432,902,008,176,640,000 is the largest factorial that fits in a long long; 21! does not. So the formula already fails for C(21, 10), which is only 352,716. The triangle, which never holds anything larger than the answers themselves, gets all the way to row 66 before a cell overflows.
Running it yourself
gcc -std=c11 -Wall -Wextra -pedantic choose.c -o choose
./chooseIt prints recursive C(5, 2) = 10 in 19 calls and table C(5, 2) = 10.
Worked example
Row 6 from row 5. Row 5 is 1, 5, 10, 10, 5, 1. Each inner cell of row 6 is the sum of the two above it: 1 + 5 = 6, 5 + 10 = 15, 10 + 10 = 20, 10 + 5 = 15, 5 + 1 = 6. With a 1 at each end, row 6 is 1, 6, 15, 20, 15, 6, 1, so C(6, 3) = 20.
A lottery draw. Choosing 6 numbers from 49 can be done in C(49, 6) = 13,983,816 ways, so one ticket has about a 1 in 14 million chance. The triangle gives it after building 49 rows.
The largest the triangle can go. Row 66 is the last row whose cells all fit in a long long. Its middle cell is C(66, 33) = 7,219,428,434,016,265,740. In row 67, C(67, 33) would overflow.
Before you read on, two to try:
- How many calls does
choose_rec(6, 3)make? (39: 2 × 20 − 1.) - Why does
choose_rowupdate the row from the right? (From the left,row[j]would add the newrow[j − 1], already overwritten, instead of the old one.)
Where it’s used
Counting in probability. The chance of a hand of cards or a lottery ticket comes down to C(n, r); see Counting.
Powers of a sum. Row n of the triangle gives the coefficients of (a + b)ⁿ: (a + b)² = a² + 2ab + b², and (a + b)⁵ has the coefficients 1, 5, 10, 10, 5, 1. That is where the name “binomial” comes from.
The binomial distribution. The chance of exactly r heads in n tosses of a fair coin is C(n, r) / 2ⁿ.
Tables filled from the row above. Building each row from the one before, and keeping only one row, is a common pattern in dynamic programming, the method of Memoisation (4.7).
Reference card
| Idea | In this lesson |
|---|---|
| C(n, r) | the ways to choose r of n things, order ignored |
| rule | C(n, r) = C(n − 1, r − 1) + C(n − 1, r) |
| base cases | C(n, 0) = C(n, n) = 1 |
| plain recursion | 2C(n, r) − 1 calls; C(5, 2): 19 |
| one row | build each row from the one above, updating from the right |
| table cost | n(n − 1)/2 additions; one row of n + 1 cells |
| formula | n! / (r! (n − r)!): 21! already overflows a long long |
| limits | the triangle reaches row 66, C(66, 33) = 7,219,428,434,016,265,740 |
Platform: C11, gcc on x86-64 Linux, long long 8 bytes.