組み合わせ

順列と組み合わせの違い

たとえば「A・B・Cの3人から2人を選んでリレーの走順を決める」と「A・B・Cの3人から2人を選んで委員にする」では、何が違うでしょうか？

リレーの走順：{A→B} と {B→A} は別の走順（AとBの並ぶ順番が違う）
委員：{A, B} と {B, A} は同じ選択（どちらもAとBが委員になる）

前回学んだ順列は「順序あり」の選び方でした。たとえば「A・B・C」と「B・A・C」は違う並び方として数えます。

しかし「A・B・Cの3人のうち2人を選ぶ」だけなら、{A,B}と{B,A}は同じ選択です。このように順序を考えない選び方の数を組み合わせ（コンビネーション）といいます。

P(n,r) ÷ r! = C(n,r)

順列の数を、r個の並び替え数（r!）で割れば組み合わせになる

「順列は組み合わせの何倍あるか？」——それが $r!$ 倍です。 $r$ 個を並び替える通り数だけ、組み合わせの各ケースが重複して数えられているからです。

C(n,r) の公式

$C(n,r) = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}$

式	値
$C(5,2)$	$\frac{5!}{2!\cdot3!} = \frac{120}{2 \times 6} = 10$
$C(6,3)$	$\frac{720}{6 \times 6} = 20$
$C(10,4)$	$\frac{10!}{4!\cdot6!} = 210$

重要な性質：

$C(n, 0) = C(n, n) = 1$ （「誰も選ばない」方法は1通り、「全員選ぶ」方法も1通り）
$C(n, r) = C(n, n-r)$ （「r人選ぶ」＝「残りの(n-r)人を除く」なので同じ数）

この対称性は計算を楽にしてくれます。例えば $C(10, 7) = C(10, 3) = 120$ ——7人選ぶのと3人「外す」のは同じことです。

パスカルの三角形

パスカルの三角形は C(n,r) の値を三角形状に並べたものです。

C(0,0) = 1
C(1,0) C(1,1) = 1 1
C(2,0) C(2,1) C(2,2) = 1 2 1
C(3,0) ... = 1 3 3 1
C(4,0) ... = 1 4 6 4 1

漸化式： $C(n,r) = C(n-1,r-1) + C(n-1,r)$

隣り合う2つの値の和が、その下の値になります。これは「n番目の人を選ぶか選ばないか」の2択から導かれます——「 $n$ 番目を選んで残り $r-1$ 人を選ぶ場合の数」＋「 $n$ 番目を選ばずに残りから $r$ 人を選ぶ場合の数」です。

パスカルの三角形インタラクティブデモ

マウスを左右に動かすと、ハイライトされる列が変わります。各行の値を観察してください。各行の数を全部足すと $2^n$ になっていることも確認してみましょう（ $n$ 行目の場合）。

パスカルの三角形：マウスで列をハイライト、C(n,r)の値を確認

var ROWS = 10;

function fact(n) {
var f = 1;
for (var i = 2; i <= n; i++) f *= i;
return f;
}

function C(n, r) {
if (r < 0 || r > n) return 0;
return fact(n) / (fact(r) * fact(n - r));
}

function loop() {
ctx.clearRect(0, 0, W, H);

var cellW = 54;
var cellH = 34;
var topY = 20;

var hovCol = Math.round((mx / W) * ROWS);
hovCol = Math.max(0, Math.min(ROWS, hovCol));

for (var n = 0; n <= ROWS; n++) {
  for (var r = 0; r <= n; r++) {
    var x = W / 2 + (r - n / 2) * cellW;
    var y = topY + n * cellH;
    var val = C(n, r);

    var isHov = (r === hovCol);
    var isDiag = (n === r) || (r === 0);

    if (isHov) {
      ctx.fillStyle = '#f59e0b';
    } else if (isDiag) {
      ctx.fillStyle = '#3b82f644';
    } else {
      ctx.fillStyle = '#1e293b';
    }

    ctx.beginPath();
    ctx.roundRect(x - cellW / 2 + 2, y - 12, cellW - 4, cellH - 4, 4);
    ctx.fill();

    ctx.fillStyle = isHov ? '#1e293b' : '#e2e8f0';
    ctx.font = (isHov ? 'bold ' : '') + '12px monospace';
    ctx.textAlign = 'center';
    ctx.fillText(val, x, y + 4);
  }
}

ctx.fillStyle = '#94a3b8';
ctx.font = '13px sans-serif';
ctx.textAlign = 'center';
ctx.fillText('列 r = ' + hovCol + ' をハイライト中', W / 2, 370);
}

function loopWrap() {
loop();
requestAnimationFrame(loopWrap);
}
loopWrap();

C(n,r) の具体的な使い方

例題1：委員の選出

10人のクラスから委員を3人選ぶ方法は何通り？

「誰が委員になるか」だけが重要で、「どの順番で選ばれるか」は関係ありません。これは組み合わせです。

$C(10,3) = \frac{10 \times 9 \times 8}{3!} = \frac{720}{6} = 120 \text{ 通り}$

例題2：トランプの組み合わせ

52枚のトランプから5枚を引く場合の数は？

ポーカーやブラックジャックで「どの5枚が手に入るか」を数える問題です。

$C(52,5) = \frac{52!}{5! \cdot 47!} = 2{,}598{,}960 \text{ 通り}$

260万通り近くもあるのですね。

例題3：対称性の利用

$C(10,7) = C(10,3) = 120$

「7人選ぶ」＝「残り3人を選ばない」なので同じ数になります。大きい方より小さい方で計算する方が楽です。

組み合わせと確率

組み合わせは確率計算で頻繁に使われます。

例：10本のくじのうち3本が当たりです。3本引くとき、ちょうど2本当たる確率は？

まず「どの3本を引くか」の全体の場合の数、次に「そのうち当たり2本・はずれ1本の場合の数」を数えます。

全体の場合の数： $C(10,3) = 120$
当たり3本から2本選ぶ： $C(3,2) = 3$
はずれ7本から1本選ぶ： $C(7,1) = 7$
ちょうど2本当たる場合の数： $3 \times 7 = 21$

$P(\text{ちょうど2本当たり}) = \frac{21}{120} = \frac{7}{40} = 0.175$

二項係数との関係

$(a+b)^n$ を展開したときの係数はパスカルの三角形と一致します。

$（a+b)^n = \sum_{r=0}^{n} C(n,r)\, a^{n-r} b^r$

例： $(a+b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$

係数 $1, 4, 6, 4, 1$ はパスカルの三角形の第4行（ $n=4$ の行）です。これは「 $n$ 個の $(a+b)$ の掛け算から $b$ を $r$ 個選ぶ方法」が $C(n,r)$ 通りある、という考え方から来ています。

まとめ

組み合わせ C(n,r)：「誰が選ばれるか」だけが重要で順序は関係ない選び方
公式： $C(n,r) = \frac{n!}{r!(n-r)!} = \frac{P(n,r)}{r!}$ （順列を並び替え数で割る）
$C(n,r) = C(n, n-r)$ の対称性を活用すると計算が楽になる
パスカルの三角形は C(n,r) の値の配置で、漸化式 $C(n,r) = C(n-1,r-1)+C(n-1,r)$ で構成される
組み合わせは確率計算・二項定理の基礎になる

次回からいよいよ確率の基本に入ります。