2.3.1. 組み合わせ¶

Code: combination.py

Test: test_combination.py

組み合わせとは¶

Combination (Wikipedia)

ものを取り出すときの、取り出し方のことをいう。

順列において並び方を無視したものともいえる。

組み合わせの場合の数¶

\(n\) 個から \(k\) 個を取り出すとき、組み合わせの場合の数は記号 \(_nC_k\) や \(C(n,k)\) もしくは \(\binom{n}{k}\) で表される。

右辺は分子・分母ともに \(k\) 個の数の積となっている。

\[C(n,k) = \frac{P(n, k)}{k!} = \frac{n \times (n-1) \times \ldots \times (n-k+1)}{k \times (k-1) \times \ldots \times 1}\]

階乗だけを用いて、次のように表すこともできる。

\[C(n,k) = \frac{n!}{k!(n-k)!}\]

1つ目の式は次のように解釈できる。

\(n\) 個から \(k\) 個を取り出し、順番に並べる (\(P(n, k)\) 通り)
同じ要素が含まれている \(k!\) 通りの並べ方を、まとめて1通りとみなす (\(k!\) で割る)

実装¶

概要¶

素数の法 \(p\) のもとで、組み合わせの場合の数 \(C(n, k)\) を求める。

実装のポイント¶

階乗を予め計算しておくことで、クエリ計算量 \(\mathcal{O}(1)\) で計算できる。

計算量¶

前処理
- list_mod_facts(n, p) \(\mathcal{O}(n)\)
- list_mod_inv_facts(n, p) \(\mathcal{O}(n + \log{n})\)
クエリ
- mod_comb(n, k, p) \(\mathcal{O}(1)\)

コード¶

[1]:

from __future__ import annotations


def list_mod_facts(n: int, p: int) -> list[int]:
    f = [1 for i in range(n+1)]
    for i in range(2, n+1):
        f[i] = f[i-1] * i % p
    return f


def list_mod_inv_facts(n: int, p: int) -> list[int]:
    invf = [1 for i in range(n+1)]
    fn = 1
    for i in range(2, n+1):
        fn = fn * i % p
    invf[n] = pow(fn, p-2, p)
    for i in range(n, 2, -1):
        invf[i-1] = invf[i] * i % p
    return invf


def mod_comb(n: int, k: int, p: int, f: list[int], invf: list[int]) -> int:
    c = f[n]
    c = c * invf[n-k] % p
    c = c * invf[k] % p
    return c

使用例¶

[2]:

f = list_mod_facts(100000, 1000000007)
invf = list_mod_inv_facts(100000, 1000000007)
c = mod_comb(10, 3, 1000000007, f, invf)
print(c)