組合せ nCr

方針

解答

⓪ 発想 — どう考え始めるか。 「$3$ 人に役割の区別はない」— この一言が組合せを指名している。

$\{\mathrm{A},\mathrm{B},\mathrm{C}\}$ を選ぶのも $\{\mathrm{C},\mathrm{A},\mathrm{B}\}$ を選ぶのも、同じ $3$ 人組。順番は関係ない。

もし順番をつけて数えると(順列)、$3$ 人組 $1$ つを $3!=6$ 回も数えてしまう。だから $6$ で割って $1$ 回にする。

$${}_8{\mathrm{C}}_3=\frac{{}_8{\mathrm{P}}_3}{3!}=\frac{8\times 7\times 6}{3\times 2\times 1}=\frac{336}{6}=56$$

分母は $3$ ではなく $3!=6$。 ここを間違えないこと。

「選ぶだけか、並べるまでか」 — 問題文にその答えは必ず書いてある。

3人に役の区別がないので、選ぶ順番は関係ない。こういうときは組合せ ${}_8{\mathrm{C}}_3$ を使う。

$${}_8{\mathrm{C}}_3=\frac{8\times 7\times 6}{3\times 2\times 1}=\frac{336}{6}=56(\text{通り})$$

分母の $3!=6$ で割る意味を確かめておこう。もし役を区別して並べるなら ${}_8{\mathrm{P}}_3=8\times 7\times 6=336$ 通り。でも同じ3人組は、並べ方が $3!=6$ 通りあって、その6通りが全部ダブって数えられている。この順番の違いを消すために6で割る。

$${}_8{\mathrm{C}}_3=\frac{{}_8{\mathrm{P}}_3}{3!}$$

まとめ:「順番を区別すれば順列、区別しなければ組合せ($r!$ で割る)」。この対応が、場合の数の背骨になる。

発展 — 一歩先へ。 組合せの数 ${}_n{\mathrm{C}}_r$ は、数IIで学ぶ二項定理の係数として再登場する。

$$(a+b{)}^n=\sum _{r=0}^n{}_n{\mathrm{C}}_r{a}^{n-r}{b}^r$$

なぜ組合せが出てくるのか。$(a+b{)}^8$ を展開するとき、$8$ 個の $(a+b)$ からどの $3$ 個で $b$ を選ぶかを決めれば、$a^5{b}^3$ の項が $1$ つできる。その選び方は ${}_8{\mathrm{C}}_3=56$ 通り — だから $a^5{b}^3$ の係数は $56$ になる。

「展開の係数」と「選び方の数」が同じものだと分かると、代数と数え上げが一本につながる。だから ${}_n{\mathrm{C}}_r$ は二項係数とも呼ばれる。

パスカルの三角形の各段が $(a+b{)}^n$ の係数になっているのも、この対応の帰結だ。$1,4,6,4,1$ は $(a+b{)}^4=a^4+4a^{3}b+6a^2{b}^2+4a{b}^3+b^4$ の係数そのものである。

数える(組合せ)・展開する(代数)・足し上げる(パスカル) — $3$ つの顔を持つ数が、高校数学のあちこちで待ち構えている。

別解

組合せの計算には、割り算をまったく使わない道がある。特定の $1$ 人に注目して、入るか入らないかで場合分けするやり方だ。

$\mathrm{A}$ さん $1$ 人に注目する。 掃除当番の $3$ 人組は、次の $2$ 種類しかない。

(i) $\mathrm{A}$ が当番に入る場合。 $\mathrm{A}$ はもう決まったので、残り $7$ 人から $2$ 人を選べばよい。

$${}_7{\mathrm{C}}_2=\frac{7\times 6}{2}=21(\text{通り})$$

(ii) $\mathrm{A}$ が当番に入らない場合。 $\mathrm{A}$ を除いた $7$ 人から $3$ 人を選ぶ。

$${}_7{\mathrm{C}}_3=\frac{7\times 6\times 5}{6}=35(\text{通り})$$

この $2$ つに重なりはなく、これで全部である($\mathrm{A}$ は入るか入らないかのどちらか)。だから足す。

$$21+35=56(\text{通り})$$

本解と一致した ✓。

この関係を式にすると

$${}_8{\mathrm{C}}_3={}_7{\mathrm{C}}_2+{}_7{\mathrm{C}}_3$$

一般に

$${}_n{\mathrm{C}}_r={}_{n-1}{\mathrm{C}}_{r-1}+{}_{n-1}{\mathrm{C}}_r$$

これがパスカルの法則だ。上の段の隣り合う $2$ 数を足すと、下の段の数になる — パスカルの三角形が、まさにこの式で組み上がっている。

$$\begin{array}{c}1\\ 11\\ 121\\ 1331\\ 14641\end{array}$$

掛け算も割り算も使わず、足し算だけで組合せの値が出る — 手計算でも、コンピュータでも(桁あふれしにくいので)重宝する方法である。

もう $1$ つ、計算を楽にする性質。

$${}_8{\mathrm{C}}_3={}_8{\mathrm{C}}_5=56$$

「$8$ 人から当番 $3$ 人を選ぶ」ことは、「$8$ 人から居残らない $5$ 人を選ぶ」ことと同じ — 選ぶ側を数えても、選ばれない側を数えても、通り数は変わらない。だから ${}_n{\mathrm{C}}_r={}_n{\mathrm{C}}_{n-r}$。

たとえば ${}_{100}{\mathrm{C}}_{98}$ を計算するとき、まともにやると大変だが、${}_{100}{\mathrm{C}}_2=\frac{100\times 99}{2}=4950$ と読みかえれば一瞬だ。大きいほうの $r$ が出てきたら、ひっくり返す — 実戦で効く小技である。