組合せの計算

質問

(n)C(r - 1) + (n - 1)C(r) = n! / {r! (n - r)!}

左辺から右辺への変化の過程を教えてください。

回答No.3

alice_44 · ベストアンサー

よく知られた公式　(n-1)C(r-1) + (n-1)C(r) = (n)C(r)
の間違いじゃないかな？　こっちなら、
(n)C(r) = n! / { r! (n-r)! }　を使って
左辺-右辺=0 を計算してみせれば、証明したことになる。

お礼

回答ありがとうございました。公式を証明しようと思っていた公式に不具合があったということが分かりました。正しい公式をご提示していただきありがとうございました。

回答No.4

Tofu-Yo

他の回答者さんからあったとおり(n-1)Cr+(n-1)C(r-1)=nCr…(1)の間違いだと思います。
こういう証明では、「どういう式を示せれば目的のものが示せるか」、をゴール（結論）から逆算してみるのも１つの手です。天下り式ですが効果的です。

(1)を定義に従って階乗を用いて分数表示したあと、左右辺の分母を払ってみてください。
(n-1)!・(n-r)+(n-1)!・r=n!
を示せればよいことがわかりますね。これは簡単なのですぐにできます。あとは逆を辿ることによって(1)を示せますね。

蛇足ですが直観的な意味は、次の通り。

30人のクラスにあなたがいて、
「30人から5人の委員を決めるとしたら何通りの決め方があるか」
を考えていたとします。
これは30C5だな、とわかり、計算し終えたときに、転校生が1人来てしまいます。結局
「31人から5人の委員を決めるとしたら何通りの決め方があるか」
を考えなければいけなくなりました。30C5の計算を破棄して31C5を計算するのも一つの手ですが、このときに
「30C5からどれだけ増えるのか」
を考え、30C5に合算することを考えてみましょう。1人増えた転校生は、もともといた30人のうちどの4人とも新しい5人の組み合わせを作ることができます。したがって増えるのは「30C4」ということになります。このことはつまり、

30C5+30C4=31C5

ということを表しています。

お礼

回答ありがとうございました。公式を証明しようと思っていた公式に不具合があったということが分かりました。正しい公式でやっと証明が進みました。実用性のある問題提示までしていただきありがとうございました。

回答No.2

chie65535

組み合わせの公式は

nCr=n!/{(n-r)!r!}

だから

＞(n)C(r - 1) + (n - 1)C(r) = n! / {r! (n - r)!}

という式は成り立たない。

右辺は組み合わせの公式そのままだから、この式は

(n)C(r - 1) + (n - 1)C(r) = (n)C(r)

って式と同じ。

n=3、r=2で計算してみると

3C1+2C2=3C2

となり

3+1=3

なので、式は成り立たない。

お礼

回答ありがとうございます。公式を証明しようと思っていた公式に不具合があったということが分かりました。その公式の間違いの見つけ方として、簡単な数字を代入して見ることがいいといいことが分かりました。無駄な時間を最小限に抑えることができました。ありがとうございました。

回答No.1

Tacosan

計算する.