# binomial coefficients

🏠

This algorithm is based off the formula:

Which actually works. Let's try it here:

Say we have $n = 5$ then n can be thought of as a set ${1,2,3,4,5}$. If $k = 2$ then our subsets are $\{\{1,2\},\{1,3\},\{2,3\},\{1,4\},\{2,4\},\{3,4\},\{1,5\},\{2,5\},\{3,5\},\{4,5\}\}$, i.e we have 10 subsets.

Now consider: ${n-1\choose k}$ since we drop the 5, we can simply drop all 4 subsets containing a 5: $\{\{1,2\},\{1,3\},\{2,3\},\{1,4\},\{2,4\},\{3,4\}\}$ leaving us with 6 subsets.

Now consider: ${n-1\choose k-1}$ this yields 4 subsets: $\{1\},\{2\},\{3\},\{4\}$. Now sticking the 5 back into those subsets gives us: $\{\{1,5\},\{2,5\},\{3,5\},\{4,5\}\}$, i.e the 4 subsets that went missing with ${n-1\choose k}$.

 1 from functools import lru_cache
2 from test_framework import generic_test
3
4
5 @lru_cache(None)
6 def bc(n, k):
7     if k in (0, n):
8         return 1
9     without_k = bc(n - 1, k)
10     with_k = bc(n - 1, k - 1)
11     return without_k + with_k
12
13 if __name__ == "__main__":
14     exit(
15         generic_test.generic_test_main(
16             "binomial_coefficients.py", "binomial_coefficients.tsv", bc
17         )
18     )