# 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}$.

 1from functools import lru_cache
2from test_framework import generic_test
3
4
5@lru_cache(None)
6def 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
13if __name__ == "__main__":
14    exit(
15        generic_test.generic_test_main(
16            "binomial_coefficients.py", "binomial_coefficients.tsv", bc
17        )
18    )