組み合わせの問題について

質問

組み合わせに関する問題で質問があります。

∑n_C_k = 2^n　　（※∑はk=0からnまで）

の証明がわかりません。

帰納法をつかってやるのかなと試してみたのですが、
n=kが成立すると仮定してn=k+1を計算するところで
詰まってしまいました。

よろしくお願いします。

回答No.4

tmpname · ベストアンサー

まあNo1さんが書いておられますが、例えば

＊先ず、「(n+1)個のものから(r+1)個のものを選ぶ組み合わせの数」（但しn>r）を考える。この時、(n+1)個のものの中の適当な一つをAと名づけておくと、「(n+1)個のものから(r+1)個のものを選ぶ」には、
1. A以外のn個から(r+1)個を選ぶ
2. Aを選び、それ以外のn個から残りr個を選ぶ
2つのやり方があって、よって(n+1)C(r+1) = nC(r+1) + nCr (D)が成り立つ（計算でも確かめてみましょう）

そこで、Σ[0≦k≦n] nCk = 2^n (B)について、数学的帰納法で示す
a. n=1の時 計算で確かめる
b. n=mの時成立するとして、n=m+1の時

Σ[0≦k≦m+1] (m+1)Ck
= (m+1)C0 + Σ[1≦k≦m] (m+1)Ck　+ (m+1)C(m+1)
= 2 + Σ[0≦r≦m-1] (m+1)C(r+1) [k=r+1とおく]
= 2 + Σ[0≦r≦m-1]mC(r+1) + Σ[0≦r≦m-1]mCr [(D)を使う]
= 2 + Σ[1≦k≦m]mCk + Σ[0≦r≦m-1]mCr [k=r+1]
= Σ[0≦k≦m]mCk + Σ[0≦r≦m]mCr
= 2^m + 2^m [帰納法仮定]
= 2^(m+1)
となって、n=m+1の時もOK

お礼

ありがとうございます。
私が個人的に一番理解しやすかった証明なので、
tmpnameさんをベストアンサーにさせて頂きます。

みなさん、ありがとうございました。

回答No.3

kabaokaba

>帰納法でやるとしたら、どのようにやるのでしょうか。

例えば，実験してみればいい
n=1のとき
1+1 = 2
n=2のとき
1+2+1 = 1+(1+1)+1 = 1 + 2 + 1 = 4 = 2^2
n=3のとき
1+3+3+1 = 1 + (1+2) + (2+1) + 1
= 1+(1+2+1)+1 + 2 = (1+2+1)+(1+2+1) = 2*2^2 = 2^3
n=4のとき
1+4+6+4+1 = 1+(1+3)+(3+3)+(3+1) +1
= (1+3+3+1) + (1+3+3+1) = 2*2^3=2^4
n=5のとき
1+5+10+10+5+1
= 1+(1+4)+(4+6)+(4+6)+(4+1)+1
= (1+4+6+4+1)+ (1+4+6+4+1)
= 2*2^4 = 2^5

パスカルの三角形で
n=r+1のケースをn=rのケースに引き落として
重複する項を仕分けて，さらに
任意の自然数sに対して sC0=sCs=1
sCt=sC(s-t)（t=0,1,...,s）
であることを考えればいい．

ほかにも，もっと組合せ的に考えてもいい．

2^n というのは，要素数nの集合の部分集合の個数
nCkというのは，n個の中からk個を選び出す組合せ，すなわち
要素数nの集合の「要素数がkである部分集合」の個数
だから
nCkを全部足すと2^nになる

お礼

丁寧にご回答いただきまして、
ありがとうございます。
とても助かりました。

回答No.2

ferien

＞∑n_C_k = 2^n　　（※∑はk=0からnまで）
左辺は２項定理を使って書き換えられるので、
左辺＝nＣ0＋nＣ1＋……＋nＣn
＝nＣ0１^n・１^0＋nＣ1１^(n-1)・１＋……＋nＣn１^0・１^n
＝（１＋１）^n
＝２^n
＝右辺

が成り立ちます。

お礼

二項定理に書き換えられることをすっかり忘れていました。
ありがとうございました。

回答No.1

kabaokaba

二項定理(1+x)^nでx=1を代入

もちろん帰納法でもできる
nCk = (n-1)Ck + (n-1)C(k-1)　(たぶん添え字はこれでいいはずだが要確認)
いわゆるパスカルの三角形を使うと思うが
書くのがめんどくさい

お礼

ありがとうございます。

補足

kabaokabaさん、ありがとうございます。
帰納法でやるとしたら、どのようにやるのでしょうか。