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     )