みさご解体新書

組み合わせ

コード例

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<vector<ll>> comb;
// パスカルの三角形を利用して組み合わせを前計算する
void init_nCk(int n) {
  n++;  // nCkを計算するにはn+1の領域が必要

  // n*nの領域を確保
  comb.resize(n, vector<ll>(n, 0));
  // パスカルの三角形の上端は1 (0C0)
  comb[0][0] = 1;
  for (int i = 1; i < n; i++) {
    // どの行も左端と右端は1になる nC0 = nCn = 1
    comb[i][0] = 1;
    comb[i][i] = 1;
    // 端以外の場所の組み合わせ数は、自身の左上と右上の組み合わせ数を足したものになる
    for (int j = 1; j < n - 1; j++) {
      comb[i][j] = (comb[i - 1][j - 1] + comb[i - 1][j]);
    }
  }
}
ll nCk(int n, int k) { return comb[n][k]; }

// nC2はよく利用するので単独で定義
ll nC2(ll n) { return n * (n - 1) / 2; }

int main() {
  init_nCk(4);
  cout << nCk(3, 2) << endl;  // 3
  cout << nCk(4, 4) << endl;  // 1
}

パスカルの三角形 を利用した組み合わせ計算関数。

init_nCk(n) で nC0_n \mathrm{C} _0 ～ nCn_n \mathrm{C} _n までの組み合わせ数を前計算しておき、実際の利用は nCk(n, k) で行う。

解説/アルゴリズム

異なる n 個のものから異なる r 個を選んで作った集合をn個からr個とった組み合わせといい、組み合わせの総数を nCr_n \mathrm{C} _r で表す。

たとえば a, b, c, d という 4 つの文字の中から 3 つの文字を選んで集合を作る場合、

{a, b, c}, {a, c, d}, {b, c, d}, {a, b, d}

この 4 つの集合を作ることができるので、 4C3=4_4 \mathrm{C} _3 = 4 になる。

順列との違い

順列の場合、取り出す順番を区別するので、例えば上記の{a, b, c}という組み合わせに対して、

{a, b, c}, {a, c, b}, {b, a, c}, {b, c, a}, {c, a, b}, {c, b, a}

の 6 通りの順列がある。

この 6 通りの 6 は 3 x 2 x 1 、つまり 3! であり、 3 つの文字を選んだので順列は 3! になる。

他の組み合わせ 3 通りに対しても、それぞれ 6 通りの順列があることになるので、組み合わせと順列の関係は、

4C3×3!=4P3_4 \mathrm{C} _3 \times 3! = {_4 \mathrm{P} _3}

両辺を 3!で割ると、

4C3=4P33!_4 \mathrm{C} _3 = \dfrac{_4 \mathrm{P} _3}{3!}

計算してみると、

4C3=4P33!=4×3×23×2×1=4_4 \mathrm{C} _3 = \dfrac{_4 \mathrm{P} _3}{3!} = \dfrac{4 \times 3 \times 2}{3 \times 2 \times 1} = 4

一般化すると次のようになる。

nCr=nPrr!_n \mathrm{C} _r = \dfrac{_n \mathrm{P} _r}{r!}

変形

n 個のものから r 個選ぶということは、他の n - r 個を残す、つまり残す n - r 個を選ぶということと同じなので、次の等式が成り立つ。

nCr=nCn−r_n \mathrm{C} _r = {_n \mathrm{C} _{n-r}}

これは便利な変形で、たとえば 100C99_{100} \mathrm{C} _{99} を求める場合、 100C1_{100} \mathrm{C} _1 に変形して、結果が 1 とすぐにわかるので、複雑な計算をしなくて済む。

  • 100C0=100C100_{100} \mathrm{C} _{0} = {_{100} \mathrm{C} _{100}}
  • 100C1=100C99_{100} \mathrm{C} _{1} = {_{100} \mathrm{C} _{99}}
  • 100C2=100C98_{100} \mathrm{C} _{2} = {_{100} \mathrm{C} _{98}}

という風に、組み合わせの数は山型になるので、 nCr_n \mathrm{C} _r の r が自由に選べるとき、一番大きい数になるのは nCn2_n \mathrm{C} _{\frac{n}{2}} となる。

関連記事