nCr の等式は同じものを 2 通りに数えた結果

${}_n{\mathrm{C}}_r={}_n{\mathrm{C}}_{n-r}$ を、階乗の式に直して確かめることはできます。ただ、もっと速い示し方がある。

$n$ 個から $r$ 個を選ぶことと、残す $n-r$ 個を決めることは同じ作業です。同じものを 2 通りに数えれば、それだけで等式になる。

証明の型はひとつ

組合せの等式は、たいてい次の形で示せます。

ある集合の要素の個数を、2 通りの数え方で計算する。どちらも同じ集合を数えているので、2 つの式は等しい。

式変形は要りません。何を数えているかを言葉で言い切れば終わります。

対称性の等式

$n$ 人から $r$ 人の委員を選びます。選び方は ${}_n{\mathrm{C}}_r$ 通り。

同じことを、残る $n-r$ 人を決める作業と見ることもできます。こちらは ${}_n{\mathrm{C}}_{n-r}$ 通り。

選ぶ側と残す側は 1 対 1 に対応するので、両者は等しい^[1]。

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

パスカルの規則

$n$ 人から $r$ 人を選ぶ選び方を、特定の 1 人 A を含むかどうかで分けます。

A を含むなら、残り $r-1$ 人を A 以外の $n-1$ 人から選ぶ。${}_{n-1}{\mathrm{C}}_{r-1}$ 通り。

A を含まないなら、$r$ 人すべてを A 以外の $n-1$ 人から選ぶ。${}_{n-1}{\mathrm{C}}_r$ 通り。

この 2 つで全体を過不足なく覆っています^[1]。

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

パスカルの三角形で、上の 2 つの数を足すと下の数になる規則が、この等式にあたります。

行の和

$n$ 個の要素をもつ集合の部分集合を数えます。要素ごとに入れるか入れないかを決めるので $2^n$ 個^[3]。

同じものを、要素の個数で分類しても数えられます。$r$ 個の部分集合が ${}_n{\mathrm{C}}_r$ 個あるので、$r$ を 0 から $n$ まで足す。

$${}_n{\mathrm{C}}_0+{}_n{\mathrm{C}}_1+\cdots +{}_n{\mathrm{C}}_n=2^n$$

$n=4$ なら $1+4+6+4+1=16$ です^[1]。

委員長を選ぶ等式

$n$ 人から $r$ 人の委員を選び、そのうち 1 人を委員長にします。この組の総数を 2 通りに数える。

先に委員を選んでから委員長を決めるなら、${}_n{\mathrm{C}}_r\times r$ 通り。

先に委員長を決めてから残りの委員を選ぶなら、$n\times {}_{n-1}{\mathrm{C}}_{r-1}$ 通り。

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

$n=5$、$r=2$ で確かめます。左辺は $2\times 10=20$、右辺は $5\times 4=20$^[1]。

斜めに足す等式

パスカルの三角形を斜めにたどって足すと、1 つ下の数になります。

$1$ から $6$ までの数から 3 個を選ぶ選び方を、いちばん大きい数で分類します。

いちばん大きい数が $m$ なら、残り 2 個は $1$ から $m-1$ までから選ぶ。${}_{m-1}{\mathrm{C}}_2$ 通りです。

$m$ は 3 から 6 まで動くので、足すと次のようになる。

$${}_2{\mathrm{C}}_2+{}_3{\mathrm{C}}_2+{}_4{\mathrm{C}}_2+{}_5{\mathrm{C}}_2={}_6{\mathrm{C}}_3$$

左辺は $1+3+6+10=20$、右辺も 20 です^[1]。

2 つの集団から選ぶ等式

男子 5 人と女子 4 人の合わせて 9 人から、3 人を選びます。${}_9{\mathrm{C}}_3=84$ 通り。

同じものを、男子が何人入るかで分類します。男子 $j$ 人と女子 $3-j$ 人を選ぶので ${}_5{\mathrm{C}}_j\times {}_4{\mathrm{C}}_{3-j}$ 通り。

$j$ を 0 から 3 まで動かして足します。

$${}_5{\mathrm{C}}_0{}_4{\mathrm{C}}_3+{}_5{\mathrm{C}}_1{}_4{\mathrm{C}}_2+{}_5{\mathrm{C}}_2{}_4{\mathrm{C}}_1+{}_5{\mathrm{C}}_3{}_4{\mathrm{C}}_0$$

$4+30+40+10=84$ で一致しました。ヴァンデルモンドの等式と呼ばれる形です^[1]。

二乗の和

男子 4 人と女子 4 人から 4 人を選びます。${}_8{\mathrm{C}}_4=70$ 通り。

男子が $j$ 人なら女子は $4-j$ 人。${}_4{\mathrm{C}}_j\times {}_4{\mathrm{C}}_{4-j}$ 通りです。

ここで ${}_4{\mathrm{C}}_{4-j}={}_4{\mathrm{C}}_j$ という対称性を使うと、各項が二乗になります。

$${}_4{\mathrm{C}}_0^2+{}_4{\mathrm{C}}_1^2+{}_4{\mathrm{C}}_2^2+{}_4{\mathrm{C}}_3^2+{}_4{\mathrm{C}}_4^2={}_8{\mathrm{C}}_4$$

$1+16+36+16+1=70$。対称性の等式を 1 回はさむだけで、二乗の和が出ます。

式変形との比べ方

階乗の式に直して計算しても、同じ等式は出ます。ただし手間が増え、意味が見えなくなる。

パスカルの規則を式変形で示すなら、通分して整理する数行が要ります。数え方の言いかえなら 2 文で済む。

答案でどちらを書くかは自由です。ただ、思い出せなくなったときに復元できるのは、数え方のほうになります。

例：等式を自分で作る

数え方を 2 通り思いつけば、新しい等式が作れます。

$n$ 人から偶数人を選ぶ選び方と、奇数人を選ぶ選び方を比べます。$n\ge 1$ なら、この 2 つは等しくなる。

特定の 1 人 A に注目します。A 以外の $n-1$ 人の選び方を先に決め、そのあと、選んだ人数が偶数になるように A を入れるかどうかを決める。

A 以外の選び方それぞれについて、偶数になる選び方と奇数になる選び方が 1 つずつ対応します。だから同数で、どちらも $2^{n-1}$ 通り。

よくある誤り

同じものを 2 通りに数える。この 1 手だけで、教科書に並ぶ等式のほとんどが示せます。

参考文献

^[1] が二項係数の主な等式、^[2] が組合せの定義、^[3] が部分集合の個数、^[4] と ^[5] が各国語での整理です。