はじめに
異なるn個のものの中からr個を選ぶ場合の数を組み合わせと呼ぶことにし、以下のようにあらわす。
{}_n C _r = \frac{n!}{r!(n-r)!}
pythonで${}_n C _r$を求める方法をいくつか取り上げる。
mathモジュールから自作
mathモジュールには組み合わせを直接求める関数がないため、上にあげた定義に基づき関数を作成する。
combination_1.py
import math
def comb(n, r):
return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
base = comb(5,3)
print(base) # 10
scipyの組み込み関数
組み合わせの数を最も簡単に求められる方法。
scipy.special.comb — SciPy v1.3.0 Reference Guide
https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html
combination_2.py
from scipy.special import comb
base = comb(5, 3, exact=True)
print(base) # 10
itertoolsの組み込み関数
組み合わせをそのものを具体的に用意し、組み合わせの数を調べ${}_n C _r$を得る。組み合わせの数のみを求める場合はやや非効率。
combination_3.py
from itertools import combinations
base = list(combinations("abcde",3))
print(base) #[('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'b', 'e'), ('a', 'c', 'd'), ('a', 'c', 'e'), ('a', 'd', 'e'), ('b', 'c', 'd'), ('b', 'c', 'e'), ('b', 'd', 'e'), ('c', 'd', 'e')]
print(len(base)) # 10
nを固定してrの変化を求める場合
nを固定し$(0\leq\ r \leq\ n)$でrを変化させ複数の${}_n C _r$を求めるとき、連続する${}_n C _r$、${}_n C _{r+1}$$(0\leq\ r \leq\ n-1)$の二項間漸化式としてそれぞれを求める方法を考える。
{}_n C _r = \frac{n!}{r!(n-r)!}\\
{}_n C _{r+1} = \frac{n!}{(r+1)!(n-r-1)!}\\
\frac{{}_n C _{r+1}}{{}_n C _r} = \frac{n!}{(r+1)!(n-r-1)!} \frac{r!(n-r)!}{n!} = \frac{n-r}{r+1}\\
{}_n C _{r+1} = {}_n C _r \frac{n-r}{r+1}
combination_4.py
n = 5
nCr = 1
print(nCr)
for r in range(n):
nCr_1 = nCr * (n - r) // (r + 1)
nCr = nCr_1
print(nCr_1)
# 1 5 10 10 5 1
これは${}_n C _r$$(0\leq\ r \leq\ n)$を個別に計算するよりも軽快に求まる。