# binomial coefficients

This algorithm is based off the formula:

Which actually works. Let's try it here:

Say we have then n can be thought of as a set . If then our subsets are , i.e we have 10 subsets.

Now consider: since we drop the 5, we can simply drop all 4 subsets containing a 5: leaving us with 6 subsets.

Now consider: this yields 4 subsets: . Now sticking the 5 back into those subsets gives us: , i.e the 4 subsets that went missing with .

```
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 )
```