組み合わせと順列を計算する（math.comb, math.perm）｜Python

組み合わせと順列は確率・統計の基礎であり、プログラミングでもよく登場する。Python 3.8 以降では math.comb() と math.perm() で簡単に計算できる。

組み合わせ（combination）

組み合わせは「順序を考えない選び方」の数だ。 $n$ 個から $k$ 個を選ぶ組み合わせの数は $_{n} C_{k}$ または $(k n)$ と書き、次の式で求める。

$_{n} C_{k} = (k n) = \frac{n !}{k ! ( n - k )!}$

math.comb(n, k) がこれを計算する。

import math

# 5 人から 3 人を選ぶ組み合わせ
print(math.comb(5, 3))  # 10

# 52 枚のトランプから 5 枚を選ぶ（ポーカーの手札）
print(math.comb(52, 5))  # 2598960

ポーカーで配られる 5 枚の手札のパターンは約 260 万通りもある。

順列（permutation）

順列は「順序を考える並べ方」の数だ。 $n$ 個から $k$ 個を選んで並べる順列の数は $_{n} P_{k}$ と書き、次の式で求める。

$_{n} P_{k} = \frac{n !}{( n - k )!}$

math.perm(n, k) がこれを計算する。

import math

# 5 人から 3 人を選んで並べる順列
print(math.perm(5, 3))  # 60

# 10 人でリレーの走順を決める（4 人選出）
print(math.perm(10, 4))  # 5040

組み合わせと順列の違いを具体例で確認しよう。

組み合わせ comb(5, 3) = 10

A, B, C を選ぶのと C, B, A を選ぶのは同じ。順序は無関係。

順列 perm(5, 3) = 60

A→B→C と C→B→A は別の並べ方。順序が意味を持つ。

階乗との関係

math.factorial() を使って手動で計算することもできるが、comb と perm の方がシンプルで高速だ。

import math

n, k = 10, 3

# 手動で計算
comb_manual = math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
perm_manual = math.factorial(n) // math.factorial(n - k)

# 組み込み関数
comb_builtin = math.comb(n, k)
perm_builtin = math.perm(n, k)

print(comb_manual == comb_builtin)  # True
print(perm_manual == perm_builtin)  # True

二項係数としての comb

math.comb() は二項係数としても使える。二項定理 $(a + b)^{n}$ を展開したときの係数が二項係数だ。

$(a + b)^{n} = k = 0 \sum n (k n) a^{n - k} b^{k}$

たとえば $(a + b)^{4}$ の展開を求めてみよう。

import math

n = 4
coefficients = [math.comb(n, k) for k in range(n + 1)]
print(coefficients)  # [1, 4, 6, 4, 1]

これは $(a + b)^{4} = a^{4} + 4 a^{3} b + 6 a^{2} b^{2} + 4 a b^{3} + b^{4}$ の係数に一致する。この係数の並びはパスカルの三角形としても知られている。

実用例：くじ引きの確率

10 本中 3 本が当たりのくじから 2 本引くとき、2 本とも当たる確率を求める。

import math

total = 10  # くじの総数
winners = 3  # 当たりの数
draw = 2    # 引く本数

# 2 本とも当たりを引くパターン数
favorable = math.comb(winners, draw)

# 全体から 2 本引くパターン数
total_patterns = math.comb(total, draw)

probability = favorable / total_patterns
print(f'{favorable}/{total_patterns} = {probability:.4f}')  # 3/45 = 0.0667

約 6.7% の確率で 2 本とも当たりを引ける。

実用例：パスワードの組み合わせ

4 桁の暗証番号（0〜9 の数字、重複あり）と、4 文字のパスワード（a〜z の小文字、重複なし）の総数を比較してみよう。

import math

# 4 桁の暗証番号（重複あり）→ 10^4
pin_patterns = 10 ** 4
print(f'暗証番号: {pin_patterns:,} 通り')  # 10,000 通り

# 4 文字のパスワード（26 文字から重複なしで選んで並べる）→ 26P4
password_patterns = math.perm(26, 4)
print(f'パスワード: {password_patterns:,} 通り')  # 358,800 通り

重複を許さない 4 文字パスワードの方が 35 倍以上のパターンがあり、総当たり攻撃に強い。

Python 3.7 以前の場合

math.comb() と math.perm() は Python 3.8 で追加された。それ以前のバージョンでは scipy.special.comb() や手動計算を使う。

# Python 3.7 以前での代替
import math

def comb(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))

def perm(n, k):
    return math.factorial(n) // math.factorial(n - k)

可能であれば Python 3.8 以降にアップグレードして、標準ライブラリの関数を使う方がよい。