重複組み合わせの公式で・・・

質問

n-1＋rＣr
という公式がありますが
どうやって導かれたのかが知りたいんですが、
どうやって、導かれた公式なのでしょうか？？
ＯＯＯＯＯ│ＯＯＯ│ＯＯＯＯＯＯＯＯ
↑
こんな感じに問題集の解答は説明してありました。

問題
りんご、バナナ、みかんの三種類の果物で１６こ盛りの果物かごを作るとき、その組み合わせは何通りあるか。

（１）入らない果物があってよい

どうぞよろしくお願いします。

回答No.2

age_momo · ベストアンサー

重複組み合わせの考え方は昔から色々工夫されていたみたいです。
詳しくはURLを参考にしてください。

問題集の解説はこの中で『丸棒分配法』です。

参考URL：

http://www.nikonet.or.jp/spring/repeat/repeat.htm

回答No.1

freedom560

nＨm＝m+n-1Ｃm＝m+n-1Ｃn-1 というやつですね？

問題を具体例に考えてみましょう。

ＯＯＯＯＯ│ＯＯＯ│ＯＯＯＯＯＯＯＯ
は
│の左側にある○がりんご
│と│の間にある○がバナナ
│の右側にある○がみかんになると思ってください。

すると、最初に○１６個　つまり
○○○○○○○○○○○○○○○○
を考えておいて、この中に適当に│を２本書けばそれを全て考えればこの問題が解けたことになります。

例えば
ＯＯＯＯＯ│ＯＯＯ│ＯＯＯＯＯＯＯＯ
はりんご５個、バナナ３個、みかん８個

ＯＯＯＯＯＯＯＯ││ＯＯＯＯＯＯＯＯ
はりんご８個、バナナ０個、みかん８個

│ＯＯＯＯＯＯＯＯＯＯＯＯＯＯＯＯ│
はりんご０個、バナナ１６個、みかん０個と考えます。（ここまでよろしいでしょうか？）

とすると、○１６個と│２個を適当に並べていけばいいわけですが、これは□１８個の中から○１６個、│２個を選び出すのと等価ですね。

つまり、18Ｃ2を計算すれば答えが求まるわけです。

では、最初にもどって（nＨmを）考えてみると、n個のものを重複を許してm個に分けるときは、○n個と│(m-1)個（１を引く理由はわかりますよね？）を並べればいいわけです。とすると、□(n+m-1)個の中から○n個を選ぶ、または｜(m-1)個を選ぶことと等価なので

nＨm＝m+n-1Ｃm＝m+n-1Ｃn-1

となります。