Skip to content

Instantly share code, notes, and snippets.

@CMCDragonkai
Created December 17, 2018 05:46
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save CMCDragonkai/37a8e3bc7a8ae0758246d417d5b54edc to your computer and use it in GitHub Desktop.
Combinations/Binomial Coefficients and Multi-Combinations #python
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