Created
December 17, 2018 05:46
Star
You must be signed in to star a gist
Combinations/Binomial Coefficients and Multi-Combinations #python
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import math | |
# getting combinations of choices is the same as getting the "binomial coefficient" | |
# a "binomial coefficient" is the coefficient of the x^k term in the | |
# "polynomial expansion" of the "binomial power" | |
# a binomial is a polynomial with is the sum of 2 monomials | |
# ax^m - bx^n | |
# the a and b are coefficients | |
# the m and n are distinct non-negative integers | |
# the x is the indeterminate "variable" | |
# given n, choose k | |
# the notation `(n k)` is called "binomal coefficient" | |
def choose(n, k): | |
assert n >= k and k >= 0 | |
return int(math.factorial(n) / (math.factorial(k) * math.factorial(n - k))) | |
print(choose(4, 0)) | |
print(choose(4, 1)) | |
print(choose(4, 2)) | |
print(choose(4, 3)) | |
print(choose(4, 4)) | |
# given n, multichoose k | |
# this is sometimes called the k-multi-combination | |
# basically combinations with repeats | |
# the notation is: `((n k))` | |
def multichoose(n, k): | |
return choose(n + k - 1, k) | |
print(multichoose(3, 2)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment