binomial coefficients

This algorithm is based off the formula:

$${n\choose k} = {n-1\choose k} + {n-1\choose k-1}$$

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    )