◆広島県 清川 育男さんからの解答。
箱の数をＫ、ボールの数をＭとする。
Ｋ＝２ のとき （Ｍ＋１）／１
Ｋ＝３ のとき （Ｍ＋１）×（Ｍ＋２）／（２×１）
Ｋ＝４ のとき （Ｍ＋１）×（Ｍ＋２）×（Ｍ＋３）／（３×２×１）
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・
Ｋ＝Ｎ のとき
（Ｍ＋１）×（Ｍ＋２）×（Ｍ＋３）×・・・×（Ｍ＋Ｎ−１）／（Ｎ−１）！
となる事が予想されます。
証明は数学的帰納法でおねがいします。
A2＝(m+1)/1
A3=A2*（(m+2)/2）
・・・・・・・・・・・
An=An-1*（(m+n-1)/(n-1)）
【コメント】
これはよく見るとm+n-1Ｃn-1
つまりｍ＋ｎ−１個のものから、ｎ−１個のものを取るときの組み合わせの数に一致していますね。
誰か理由を考えてくれないかなぁー。
◆京都府の大学院生 わかさひ君 さんからの解答。
以下の図において、ボールを●、区切り線を｜で示す。
ｍ個のボールを１列に並べ、それをｎ個の領域に分割することを考える。
この時、ｎ−１本の区切り線をそれぞれどこかとなりあったボールの間に置けば、ｎ個の領域に分割したことになる。
●||●●|●●●●●|●●|●●●|●● (m=15,n=7の例)
このとき、それぞれの箱に、1,0,2,5,2,3,2 個入っているのと同値。
箱の中にはボールが１個も入らない状態も許されるので、区切り線同士が隣り合うことも許される。
また、区切り線自体が端に来ることも許されるから、結局、ボールｍ個と区切り線ｎ−１個を混ぜて並び変える並べ方の総数に一致する。
したがって、 m+n-1Ｃn-1
【コメント】
明快な解答ありがとうございます。
これで帰納法を使う場合と両方、出そろいましたね。
中学生には厳しいですが、なかなか面白い問題ですね。
◆神奈川県 片山 善夫 さんからのコメント。
この問題から、
| m-1 Σ k=0 |
k+nCn = m+nCn+1 …(1) |
この問題の解を f(m,n) （m:ボール数、n:箱数）とすると、
| f(m,n) = | m Σ k=0 |
f(k,n-1) …(2) |
f(m,n) = m+n-1Cn-1 …(3)
から、(1)式が得られます。
(1)式をこの問題とは切り離して証明しようとしたのですが、お手上げでした。
(1)式がよく知られた公式でしたら、その証明をご教示願えませんでしょうか。
◆山梨県 Footmark さんからのコメント。
m+nＣn+1は、1〜(m+n)の連続(m+n)数から(n+1)数を選ぶ方法の数と一緒です。
そこで、選ぶ(n+1)数の内の最小数で場合分けすると、明かに以下になります。
最小数が １のとき、m+n-1Ｃn通り。
最小数が ２のとき、m+n-2Ｃn通り。
…………………………………………………
最小数が ｍのとき、 nＣn通り。
よって、n+(0)Ｃn＋n+(1)Ｃn＋…＋n+(m-1)Ｃn＝m+nＣn+1。
◆愛知県 Y.M.Ojisan さんからのコメント。
（１）式ですが、これは公式というよりCの再帰的定義と言っても過言ではないでしょう。
具体的に、９個から５個選ぶ組み合わせのリストを漏れなく作る場合を考えます。
漏れなくリストアップするために、各組の最大値でリストを分類すると、
｛９と１〜８から４個｝、｛８と１〜７から４個｝、｛７と１〜６から４個｝、｛６と１〜５から４個｝および｛５と１〜４から４個＝全部｝になります。
これは（１）式そのものです。（ｍ＝５、ｎ＝４）
(１＋ｘ)m+nを母関数とする方法などもありますが、上記がもっとも自然かつ自給自足な解釈と思います。
そういう方法を避け、まったく数式処理で証明する場合は
n+mCn+1＋n+mCn＝n+m+1Cn+1 を証明して、数学的帰納法を適用すればよいでしょう。
| n+mCn+1＋n+mCn＝ | (n+m)！ (n+1)！(m-1)！ |
＋ | (n+m)！ n！m！ | ＝ | (n+m)！(m+n+1) (n+1)！m！ |
＝n+m+1Cn+1 |
他にも、ぽこぺんさん出題の「二項係数 Part２」の関係などもあるようです。
なお、この問題は、重複を許してｎ個の箱からｍ個選ぶことと同じであり、重複組み合わせの基本問題です。
つまり答えはnHmです。
これにHとCの公式を用いると
nHm＝n+m-1Cm＝n+m-1Cn-1が得られます。