公開日 :
更新日 :

二項係数

\(C(n,k)\) は「\(n\) 個から \(k\) 個を選ぶ方法の数」（順番は区別しない）。
競技プログラミングでは、答えを mod で求めることが多く、階乗と逆元の階乗を前計算すれば、\(1\) 回 \(O(1)\) で計算できる。

書き方は \(C(n,k)\)、\(_nC_k\)、\((n \, k)\) などいろいろあるが、どれも同じ意味。

意味

例 ： A, B, C, D の 4 人から 2 人選ぶ

{A,B} {A,C} {A,D} {B,C} {B,D} {C,D}   → 6 通り

\(C(4, 2) = 6\) {A, B} と {B, A} は同じ選び方として 1 回だけ数える。

公式

$$C(n, k) = \frac{n!}{k! \times (n – k)!}$$

なぜこの式になるのか

\(4\) 人から \(2\) 人を「\(1\)人目、\(2\)人目」と順番を付けて選ぶと、\(4 \times 3 = 12\) 通り。
ただし、{A, B} を「A → B」「B → A」の \(2\) 回数えているので、
\(2\) 人の並べ方 \(2! = 2\) で割って \(12 \div 2 = 6\)

一般には「順番付きで \(n \times (n-1) \times \dots \times (n\,-\,k+1\)通り」を「\(k\)個の並べ方 \(k!\) 通り」で割る。

$$C(n, k) = \frac{n \times (n\,-\,1) \times \dots \times (n\,-\,k+1)}{k!}=\frac{n!}{k! \times (n – k)!}$$

性質

性質意味
\(C(n, 0) = C(n, n) = 1\)何も選ばない / 全部選ぶのは \(1\) 通り
\(C(n, 1) = n\)\(1\) 個選ぶなら \(n\) 通り
\(C(n, 1) = C(n, n\,-\,k)\)「\(k\) 個選ぶ」=「選ばない \(n\,-\,k\) 個を決める」
\(k < 0\) や \(k > n\) なら \(0\)そんな選び方はない
\(C(n, k) = C(n\,-\,1,k\,-\,1)+C(n\,-\,1, k) \)ある \(1\) 個を選ぶ場合 + 選ばない場合

計算方法の使い分け

状況方法前計算1回
\(n\) が大きい \((\sim 10^6\)、 mod あり階乗と逆元の階乗\(O(n)\)\(O(1)\)
\(n\) が大きい \((\sim 5000\)、 mod ありパスカルの三角形(mint)\(O(n^2)\)\(O(1)\)
\(n\leq66\) 、 mod なし（そのままの値がほしい）パスカルの三角形（long long)\(O(n^2)\)\(O(1)\)

コード例1 : 階乗と逆元の階乗

// n_C_k を計算する(mint)
struct combination {
  vector<mint> fact, ifact;
  combination(int n) : fact(n + 1), ifact(n + 1) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
      fact[i] = fact[i - 1] * i;          // fact[i] = i!
    }
    ifact[n] = fact[n].inv();             // ifact[n] = 1 / n!
    for(int i = n; i >= 1; i--) {
      ifact[i - 1] = ifact[i] * i;        // 1/(i-1)! = i × 1/i!
    }
  }
  mint operator()(int n, int k) {
    if(k < 0 || k > n) {
      return 0;
    } else {
      return fact[n] * ifact[k] * ifact[n - k];   // n! / (k! (n-k)!)
    }
  }
};

combination c(N);           // n ≦ N まで使える
mint x = c(N - 1, K - 1);
  • \(k < 0 || k > n\) だけで、\(n\) が負のとき（例：\(c(−1, −1)\)）も \(0\) になる。
  • 作った大きさより大きい \(n\) を渡すと範囲外アクセス。
    \(C(H+W, H)\) を使うなら combination c(H + W); のように、使う \(n\) の最大値で作る。
  • inv() は少し重い（O(log mod)）ので \(1\) 回だけ呼び、残りは後ろから掛け算で作る。

mod の世界での割り算（逆元）

余りの世界では普通に割れないので、「掛けると 1 になる数」（逆元）を掛けて割り算の代わりにする。

  • mint なら x.inv() で逆元が出る
  • 中身はフェルマーの小定理：mod p が素数なら x の逆元は x^(p−2)（x.pow(p – 2) と同じ）
  • 998244353 も 1000000007 も素数なので、どちらでも使える
  • x が mod の倍数（mint で 0）だと逆元はない。
    n が mod 以上になると n! が 0 になるので、この方法は n < mod のときだけ使える（ABC の制約ならまず問題ない）。

コード例2 : パスカルの三角形

// mint 版（n ≦ 5000 程度）
vector<vector<mint>> C(N + 1, vector<mint>(N + 1, 0));
for (int n = 0; n <= N; n++) {
    C[n][0] = 1;
    for (int k = 1; k <= n; k++) C[n][k] = C[n-1][k-1] + C[n-1][k];
}

// long long 版（n ≦ 66）
vector<vector<ll>> C(67, vector<ll>(67, 0));
// 同じ書き方

よく出る数え方

数えたいもの答え考え方
\(K\) 個選ぶとき, \(i\) を必ず含む\(C(N – 1, K – 1)\)i を確定させて、残り N – 1 個から K – 1個
\(K\) 個選ぶとき, \(i\) と \(j\) を両方含む\(C(N – 2, K – 2)\)2 個確定させる
グリッドを右と下だけで \((0,0)\)→\((H, W)\)\(C(H+W, H)\)\(H+W\) 歩のうち、どの H 歩を「下」にするか
\(N\) 種類から重複を許して \(K\) 個\(C(N+K-1, K)\)\(K\) 個の玉と \(N-1\) 本の仕切りの並べ方
\(0\) と \(1\) の並び（\(0\) がA個、\(1\) がB個）\(C(A+B, A)\)どの位置を 0 にするか
\(K\) 個を \(N\) グループに分ける（各 \(1\) 個以上）\(C(K-1, N-1)\)\(K-1\) か所のすき間から \(N-1\) か所を区切る

重複組み合わせ（仕切り）

\(3\) 種類 (a, b, c) から重複を許して \(4\) 個選ぶ = \(4\) 個の玉◯と \(2\) 本の仕切り | の並べ方。

○○|○|○   → a 2 個、b 1 個、c 1 個
||○○○○   → c 4 個

\(6\) 個の位置から仕切りの \(2\) か所を選ぶので \(C(6,2) = 15 = C(3+4-1,4)\)。

練習問題