MathMathematical Algorithms
Binomial Coefficients (Pascal's Triangle)
Count arrangements and selections: nCr via factorial and inverse-factorial tables mod p, Pascal's triangle, stars and bars, and inclusion-exclusion.
| k=0 | k=1 | k=2 | k=3 | k=4 | k=5 | k=6 | k=7 | k=8 | |
|---|---|---|---|---|---|---|---|---|---|
| n=0 | 1 | · | · | · | · | · | · | · | · |
| n=1 | · | · | · | · | · | · | · | · | · |
| n=2 | · | · | · | · | · | · | · | · | · |
| n=3 | · | · | · | · | · | · | · | · | · |
| n=4 | · | · | · | · | · | · | · | · | · |
| n=5 | · | · | · | · | · | · | · | · | · |
| n=6 | · | · | · | · | · | · | · | · | · |
| n=7 | · | · | · | · | · | · | · | · | · |
| n=8 | · | · | · | · | · | · | · | · | · |
row sums (every subset of an n-element set)
| n | row | sum | 2^n |
|---|---|---|---|
| 0 | 1 | 1 | 1 |
1/70C(n, k) counts the k-element subsets of an n-element set. Start from the only thing that is obvious: there is exactly one subset of the empty set, so C(0, 0) = 1. Everything else in the triangle follows from a single question asked about one element.
Cell being filledThe two cells it is the sum ofEdge of the triangle (always 1)ComputedValue being read off / identity being shown
PseudocodeLearn Combinatorics →
1C[0][0] = 12for n in 1 .. N:3 C[n][0] = C[n][n] = 1 # one way to choose none, one way to choose all4 for k in 1 .. n-1:5 C[n][k] = C[n-1][k-1] + C[n-1][k] # element n is either used or it is not6read C(N, K); row n sums to 2^n; C(n, k) == C(n, n-k)Variables
N8
K3
Complexity
best O(1)
avg O(1)
worst O(n^2)
space O(n)
Speed