コンビネーション

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

投稿日時 - 2007-12-27 13:27:01

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

投稿日時 - 2007-12-27 13:15:51

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

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

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

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

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

投稿日時 - 2007-12-27 02:08:13

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

投稿日時 - 2007-12-26 22:04:15

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

投稿日時 - 2007-12-26 20:57:07