コンビネーション

質問

コンビネーションの性質nCr=n-1Cr-1+n-1Cr

が成り立つ理由を教えてください。場合わけ的に考えるのだと思いますが、よくわかりません。お願いします。

回答No.3

koko_u_ · ベストアンサー

1 から n の数字の書かれたカードから r 個を取り出す方法を
「1」の書かれたカードを選ぶか否かで場合分けするのが一般的ですね。

回答No.7

Ishiwara

＃６です。補足を忘れました。
各交差点に、そこまでの経路数を書き込んで、地図を右上の方角から見ると、パスカルのピラミッドになっています。このようにして見ると、組合せや二項係数の全体像が、すべて直観的に理解できるでしょう。

お礼

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

回答No.6

Ishiwara

碁盤の目のような街路を考えます。点（0,0）から点（r,n-r）へ最短で行く経路は nCr とおりあります。
このすべての経路は、点（r, n-r-1）か点（r-1, n-r-1）のどちらかを通る必要があります。かつ、両方は通れません。
前者は n-1Cr とおりであり、後者は n-1Cr-1 とおりですから、ご質問の式が成り立ちます。

回答No.5

ikkuk

そうです。場合分けをして考えます。
具体例を用いて考えてみましょう。

リーダーを含む９人の中から４人を選びたいとします。
この選び方は9Ｃ4ですね。これが左辺にあたります。

(ア)リーダーを必ず選ぶと考えたとき
　　残りの８人から３人を選ぶから、8Ｃ3
(イ)リーダーを必ず選ばないと考えたとき
　　残りの８人から４人を選ぶから、8Ｃ4

よって、９人の中から４人を選ぶのは(ア)または(イ)より8Ｃ3＋8Ｃ4
これが右辺にあたります。

以上より9Ｃ4＝8Ｃ3＋8Ｃ4となり、９をｎにして４をｒにすると、一般論として成り立つのが分かります。

回答No.4

kumipapa

n 個の異なる物から r 個取り出すときの組み合わせの数が nＣr ですね。
n 個の中の１個に着目して考えます。順番をつけて一番前のヤツとか、一番後ろのヤツに着目する。

その１個を選んで、残りn-1個から r-1 個取り出す場合の数が　(n-1)Ｃ(r-1)
その１個を選ばずに、残りn-1個から r 個取り出す場合の数が (n-1)Ｃr
n 個から r 個取り出す場合の数は、上の２つの場合の合計だから、
nＣr = (n-1)Ｃ(r-1) + (n-1)Ｃr

回答No.2

Tacosan

nCr をどのように定義していますか?

回答No.1

info22

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