高校～組合せ

質問

区別できない同じ色の玉があり、空の箱があってもいいとき、赤玉１０個を区別できない４個の箱に分ける方法は何通りか？？という問題で地道にかいて答えを出すと２３通りという答えがでます。これが答えなのですが、この問題を計算で解くことは可能ですか？？？

回答No.2

larme001 · ベストアンサー

計算でというか考え方のコツがあります。全部書き出してみたというのならよく考えれば気付くと思いますが、どの様に書き出すと数え間違えないでしょうか？おそらく、空箱の数に注目したと思います。これを利用して、考えると一般にnコの区別できない球をr個の区別できない箱のなかにいれる場合を(=f(n,r)と表す)
１,空箱が少なくとも一つある場合。
n個の球をr-1個の箱に分けることですのでf(n,r-1)
2.空箱が一つもない場合。
それぞれの箱に一つずつ球を入れて残りのn-r個をr個に分けると考え
f(n-r,r)
の和でかけることが分かります。つまり
f(n,r)=f(n-r,r)+f(n,r-1)
これを利用して地道に数えても数えやすいものまで分解することで容易に解けるようになります。というのはたとえばf(10,2)であれば10個を2つの箱に分けるので(10,0)(9,1)(8,2)(7,3)(6,4)(5,5)の6とおりというように容易にでます。一般にf(n,2)の形までに分解することを目指せば良いでしょう。

以上のことから質問の問題も自分でやってみてと言いたいところですが、地道に数えた努力を認めて実際に解いてみますと
f(10,4)=f(6,4)+f(10,3)
=f(2,4)+f(6,3)+f(7,3)+f(10,2)
=f(2,4)+f(3,3)+f(6,2)+f(4,3)+f(7,2)+f(10,2)
=f(2,4)+f(3,3)+f(6,2)+f(1,3)+f(4,2)+f(7,2)+f(10,2)
=2+3+4+1+3+4+6
=23
となります。実践的には数え上げがしやすいところまで分解すればいいんですが、とりあえず出来る限り分解しました。

回答No.1

physicsache

解答が素数ですので、計算で出すのは困難だと思います。