組合せの公式（ちょいむず）

組合せの公式（ちょいむず）
松浦將國
2014 年 12 月 24 日
組合せの公式は挙げればきりがないが，筆者の経験でよく見かける少し難しめのものを
いくつか紹介しておく．
n C0 + n C1 + n C2 + · · · + n Cn
= 2n
(1)
ここに，n は負でない整数．n = 0 のときは明らかだから n ≧ 1 のときを考えれば良い．1
月頃に学習する予定の二項定理でも証明できるが，下記のような文章題に落とし込んでも
証明できる：1 番から n 番の箱にたかだか n 個の同型の玉を分ける場合の数 (· · · ⃝
A ) を考
える．ただし，一つの箱に入れる玉の個数は 0 か 1 とする．このとき，玉の分け方は全部
で 2n 通り．
⃝
0 箱に入れる玉の総数が 0 個のとき，玉を n 個の箱に分配する方法は n C0 通り．
⃝
1 箱に入れる玉の総数が 1 個のとき，玉を n 個の箱に分配する方法は n C1 通り．
⃝
2 箱に入れる玉の総数が 2 個のとき，玉を n 個の箱に分配する方法は n C2 通り．
..
.
⃝
n 箱に入れる玉の総数が n 個のとき，玉を n 個の箱に分配する方法は n Cn 通り．
⃝
0,⃝
1,⃝
2 , ··· ,⃝
n はどの異なる二つも両立しない事象だから，⃝
A の場合の数は n C0 + n C1 +
n C2 + · · · + n Cn
とも表せる．以上より (1) が成立する．
次の公式は大学入試などで良くみられる．
n C1 + 2n C2 + · · · + nn Cn
= n2n−1
(2)
ここで，n は正の整数．
（解 1）(2) の左辺を S とおく．ここで r = 1, 2, · · · , n に対して n Cr = n Cn−r （⃝
教 p.201, 問 14
参照）であるから
S = n Cn−1 + 2n Cn−2 + · · · + (n − 1)n C1 + nn C0 = nn C0 + (n − 1)n C1 + · · · + 2n Cn−2 + n Cn−1 .
よって，
=
=
=
=
=
2S
S +S
{n C1 + 2n C2 + · · · + (n − 1)n Cn−1 + nn Cn } + {nn C0 + (n − 1)n C1 + · · · + 2n Cn−2 + n Cn−1 }
nn C0 + {1 + (n − 1)}n C1 + · · · + {(n − 1) + 1}n Cn−1 + nn Cn
n(n C0 + n C1 + · · · + n Cn−1 + n Cn )
n2n .
ただし，最後の二行で (1) を用いた．よって，S = n2n−1 となり (2) が成立する．
（終）
（解 2）r = 1, 2, · · · , n に対して
r n Cr = r ·
n!
n · (n − 1)!
(n − 1)!
= r·
=n
= nn−1 Cr−1
r!(n − r)!
r · (r − 1)!(n − r)!
(r − 1)!{(n − 1) − (r − 1)}!
に注意すると，
S
=
=
=
nn−1 C0 + nn−1 C1 + nn−1 C2 + · · · + nn−1 Cn−1
n{n−1 C0 + n−1 C1 + n−1 C2 + · · · + n−1 Cn−1 }
n2n−1 .
最後の二行で (1) を用いた．
（終）
他にも数学的帰納法（1 月か 2 月に学習予定）を利用した証明が考えられるがここでは省
略する．また，興味がある方は下記の問題を考えてみよ．
［問題］(a) 次の等式を証明せよ (n ≧ 2)．
2n C2 + 6n C3 + · · · + n(n − 1)n Cn = n(n − 1)2n−2
（ヒント：(2) の解 2 を参考にせよ．）
(b) 次の等式を証明せよ (n ≧ 1)．
2
n C1 + 4n C2 + 9n C3 + · · · + nn Cn
= n(n + 1)2n−2
（ヒント：r(r − 1) + r = r2 .）
(c) 次の等式を証明せよ (n ≧ 3)．
6n C3 + 24n C4 + 60n C3 + · · · + n(n − 1)(n − 2)n Cn = n(n − 1)(n − 2)2n−3
(d) 次の等式を証明せよ (n ≧ 1)．
3
n C1 + 8n C2 + 27n C3 + · · · + nn Cn
= n2 (n + 3)2n−3
（ヒント：r(r − 1)(r − 2) + 3r2 − 2r = r3 .）
次の等式もよく見られる有名な公式である．
2
2
2
2
n C0 +n C1 +n C2 + · · · +n Cn
=2n Cn
(3)
n ≧ 0 のときに成立するが，n = 0 のときは自明なので n ≧ 1 のときを考えれば良い．これ
も (1) のときのような文章題にすると楽であろう：1 番から 2n 番の箱にちょうど n 個の
同型の玉を分ける場合の数 (· · · ⃝
B ) を考える．ただし，一つの箱に入れる玉の個数は 0 か
1 とする．このとき，玉の分け方は全部で 2n Cn 通り．
⃝
0 1 番から n 番の箱に入る玉の総数が 0 個のとき，n + 1 番から 2n 番の箱には n 個の玉が
入る．1 番から n 番の箱での玉の分配の仕方と n + 1 番から 2n 番の箱での玉の分配の仕方
は独立しているから，玉の分配の仕方は n C0 ·n Cn =n C20 通り（n Cr =n Cn−r より）．
⃝
1 1 番から n 番の箱に入る玉の総数が 1 個のとき，⃝
0 と同様に考えると玉の分配の仕方
は n C1 ·n Cn−1 =n C21 通り．
⃝
2 1 番から n 番の箱に入る玉の総数が 2 個のとき，⃝
0 と同様に考えると玉の分配の仕方
は n C2 ·n Cn−2 =n C22 通り．
..
.
⃝
n 1 番から n 番の箱に入る玉の総数が n 個のとき，⃝
0 と同様に考えると玉の分配の仕方
は n Cn ·n C0 =n C2n 通り．
⃝
0, ⃝
1, ⃝
2 , ···, ⃝
n の事象はどの異なる二つも両立しない．したがって，⃝
B の場合の数は
2
2
2
2
n C0 +n C1 +n C2 + · · · +n Cn
とも表せて (3) が成立する．
（終）
(3) でも二項定理を利用した証明があるがここではやらない．
最後に次の公式を紹介しておく．
n C0 +n+1 C1 +n+2 C2 + · · · +n+k Ck
=n+k+1 Ck
(4)
ここに n, k は負でない整数であるが，k = 0 のときは自明だから k ≧ 1 のときに証明する．
⃝
教 p.202, 例題 5（パスカルの三角形の公式）と n C0 =n+1 C0 = 1 を利用する．
(4) の左辺
=
=
=
=
=
(n+1 C0 +n+1 C1 ) +n+2 C2 + · · · +n+k Ck
(n+2 C1 +n+2 C2 ) + · · · +n+k Ck
···
n+k Ck−1 +n+k Ck
(4) の右辺
よって，(4) は成立．
（終）
［問題］(e) 次の等式を証明せよ：
n Cn +n+1 Cn +n+2 Cn + · · · +n+k Cn
=n+k+1 Cn+1 .
(f) 次のルールで○と×を横一列に並べる．
⃝
イ ○はちょうど 2 個使う．
⃝
ロ ×は 108 個まで使って良い．
このような並べ方は全部で何通りあるか（答：221815 通り）．