何通り？

どこかの大学の入試問題だったらしいんですが…
「区別のつかないｎ個のボールを、区別のつかない３つの箱に入れるとき、その入れ方は何通り？」
ボールも箱も区別アリ、ボールのみ区別アリ、箱のみ区別アリ、の三問は解けたんですが、最後のこの問題が解けません。誰か教えて下さい。

No.6 ベストアンサー 回答者： noname#598 回答日時： 2001/06/25 13:24

No.4の回答はやっぱり違いました。

箱に区別がつかないということは、箱に区別がつく状態から考えると、
（０，０，１）と（０，１，０）、（１，０，０）は同じと見る、ということです。
上のように２つが同じで、１つが異なる場合は３通りずつあり、
すべてが異なる場合は３！＝６通りずつあり、
すべて同じ場合は１通りしかないことから考えていきます。

n=6m-5のとき
　３つの箱に区別があるとすると(6m-3)(6m-4)/2=18m^2-21m+6 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-5 より、2a=6m-5-c この等式を満たす整数cは、c=1,3,5,…,6m-5 の3m-2通り
　実際にはcでなくてもよいから、9m-6通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、3m-2+(18m^2-21m+6-9m+6)/6=3m^2-2m 通り

n=6m-4のとき
　３つの箱に区別があるとすると(6m-3)(6m-2)/2=18m^2-15m+3 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-4 より、2a=6m-2-c この等式を満たす整数cは、c=0,2,4,…,6m-4 の3m-1通り
　実際にはcでなくてもよいから、9m-3通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、3m-1+(18m^2-15m+3-9m+3)/6=3m^2-m 通り

n=6m-3のとき
　３つの箱に区別があるとすると(6m-2)(6m-1)/2=18m^2-9m+1 通り
　a=b=cとなる１通りを除くと18m^2-9m 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-3 より、2a=6m-3-c この等式を満たす整数cは、c=1,3,5,…,6m-3 の3m-1通りだが、c=2m-1のときはa=b=cとなるので、これを除いた3m-2通り。
　実際にはcでなくてもよいから、9m-6通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、1+(3m-2)+(18m^2-9m-9m+6)/6=3m^2 通り

n=6m-2 のとき
　３つの箱に区別があるとすると3m(6m-1)=18m^2-3m 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-2 より、2a=6m-2-c この等式を満たす整数cは、c=0,2,4,,…,6m-2 の3m通り
　実際にはcでなくてもよいから、9m通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、3m+(18m^2-3m-9m)/6=3m^2+m 通り

n=6m-1　のとき
　３つの箱に区別があるとすると3m(6m+1)=18m^2+3m 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-1 より、2a=6m-1-c この等式を満たす整数cは、c=1,3,5,…,6m-1 の3m通り
　実際にはcでなくてもよいから、9m通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、3m+(18m^2+3m-9m)/6=3m^2+2m 通り

n=6mのとき
　３つの箱に区別があるとすると(6m+2)(6m+1)/2=18m^2+9m+1 通り
a=b=cとなる１通りを除くと18m^2+9m 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m より、2a=6m-c この等式を満たす整数cは、c=0,2,4,…,6m の3m+1通り
　しかし、この中には2m番目にa=b=cとなるものが含まれるので、3m通り。
　実際にはcでなくてもよいから、9m通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、1+3m+(18m^2+9m-9m)/6=3m^2+3m+1 通り

以上をまとめると、
n=6m-5のとき　3m^2-2m
n=6m-4のとき　3m^2-m
n=6m-3のとき　3m^2
n=6m-2のとき　3m^2+m
n=6m-1のとき　3m^2+2m
n=6m　のとき　3m^2+3m+1

きれいになったのできっと正しいと思います（笑）

この回答へのお礼

なるほど納得です。細かい場合分けが必要になるんですね。詳しい回答ありがとうございました。もし、もっと楽な解法を発見したらまたお願いします。

お礼日時：2001/06/25 18:56

No.8 回答者： noname#598 回答日時： 2001/06/26 08:17

No.7に書かれている、ボールに区別がついて箱に区別がつかない場合ですが、

タイプミスとは思いますが、確認します。
ちょっとまどろっこしい解き方ですが・・・・

１箇所に寄った場合は１通り
２箇所に寄った場合は(２^n-2)/2=２^(n-1)－１通り
３箇所全部に入っている場合は、まず箱に区別がつくとすると、
３^nから１箇所に偏った３通り、２箇所に偏った３＊(２^n-2)通りを引けば良い。
（２箇所の場合に３を掛けるのは、どの箱を空にするかの選び方が３通りあるから）
３^n－３＊(２^n-2)－３＝３^n－３＊２^n＋３より、
（３^n－３＊２^n＋３）／６＝（３^(n-1)＋１）／２－２^(n-1)通り

以上より、
１＋２^(n-1)－１＋（３^(n-1)＋１）／２－２^(n-1)
＝（３^(n-1)＋１）／２ 通りです。
もちろんikeshiさんの考え方の方がスマートなことは知っていますが、厳密に解いてみました。

No.6は、私の能力ではあれ以上考え方は簡単にできないです。悪しからず…

この回答への補足

すいません。タイプミスです。詳しい回答ありがとうございます。

補足日時：2001/06/26 21:19

No.7 回答者： finetoothcomb 回答日時： 2001/06/25 13:58

たびたびすみません。

下のNo.5の自分の回答のDとBを差換えさせて下さい。

【D改】ボールも箱も区別ない
n個の非個性なボールの並びを次の規則で仕切り板を入れる。(1)端にも可(2)仕切り板の左側のボールの数が右側のボールの数よりも小さくならない。このような仕切り板の入れ方　R(n)通りある。

R(n)=Σ{i=0,[n/2]}(1) ([ ]はガウス記号とする（[x]="xを越えない最大の整数"))

上記の仕切り板を入れた各状態で生じている、右側の(i個の無個性な)ボールの並びに、同様の規則で仕切りを一つ入れる。このような仕切り板の入れ方は R(i)通りある。

R(i)=Σ{j=0,[i/2]}(1)

求める場合の数は、R(n)*R(i)

R(n)*R(i)=
=Σ{i=0,[n/2]}(1* Σ{j=0,[i/2]}(1) )
=Σ{i=0,[n/2]}([i/2]+1)
=[n/2]+1+Σ{i=0,[n/2]}[i/2]

(ガウス記号の入ったこのΣってnの偶奇で展開できるのかな。）


【B改】ボールのみ区別アリ
有個性なn個のボールを、次の規則で左右に別に分ける。(1)0個も個数と考える(2)左側のボールの数が右側のボールの数よりも小さくならないようにする。このような分け方の場合の数は Q(n)通りある。

Q(n)=Σ{i=0,[n/2]}(nCi)

上記のように分けた状態で生じている、右側の(有個性なi個の）ボールを、同様の規則で左右に分ける。このようなやり方の場合の数は、Q(i)通りある。

Q(i)=Σ{j=0,[i/2]}(iCj)

求める場合の数は、Q(k)*Q(k-i)
Q(n)*Q(i)=Σ{i=0,[k/2]}(nCi *Σ{j=0,[i/2]}(iCj) )

（誰かこの後の展開やり方教えて。）

この回答への補足

展開…わかんないですねぇ。
でもＢは解けてるので、一応報告します。
「ボールも箱も区別アリ」で、ＡＢＣのうち一つにn個全部入れる場合は3通りで、箱を入れ替えると入れ替え方も３通り。その他は3^n-3通りで、箱の入れ替えはＡＢＣが異なるから６通り。よって、
(3^n-3)/6 + 3/3 = (3^n+1)/2　通りです。

補足日時：2001/06/25 18:44

No.5 回答者： finetoothcomb 回答日時： 2001/06/25 11:25

間違っていたらごめんなさい。

考えてみたことを投稿します。私にとって簡単と感じられた（思いっきり勘違いでなければ!）順番に、４問について書きます。

【A】ボールも箱も区別アリ
3^n　(通り)

【C】箱のみ区別アリ
Σ{k=0 to n} 1* Σ{i=0 to (n-k)} 1}
= Σ{k=0 to n} 1* (n-k+1)
= Σ{k=0 to n} (n+1-k)
= (n+1)Σ{k=0 to n}1 - Σ{k=0 to n} k
= (n+1)(n+1) - n(n+1)/2
= (n+1){(n+1) - n/2}
= (n+1)(n/2 +1)
= (n+1)(n+2)/2 (通り)　

【D】ボールも箱も区別ない
Yk="k個の非個性なボールの並びに対して、左側のボールの数が右側のボールの数よりも小さくならないように仕切りを１つ入れる入れ方、の場合の数"　とする。
[ ]はガウス記号とする（[x]="xを越えない最大の整数")。
Yk=[k/2]+1
An=Σ{i=0,[n/2]}(Yi) (通り)
Anを展開したものが答えになると思うのですが（検証まだ）これは展開すれば、簡単にできますもんね。

【B】ボールのみ区別アリ
"有個性なk個のボールの並びに対して、左側のボールの数が右側のボールの数よりも小さくならないように仕分けする場合の数"×"残ったボールの並びにも同様の操作をする場合の数"　を Bnとする。
[] はガウス記号とする。（[x]="xを越えない最大の整数")。
Bn=Σ{a=[n/2]+1, n}((n)C(a)) * Σ{b=[(n-k)/2]+1, n-k}((n-k)C(b)) (通り)
Bnを展開したものが答えになると思うのですが（検証まだ）もっとエレガントな方法あるのでしょうねー。

取り急ぎ投稿してみました。

No.4 回答者： noname#598 回答日時： 2001/06/25 03:09

その後気になって眠れなくなってしまい、脳の活動が止まりながらも考えました。

途中違ったらごめんなさい。
箱に区別がつかないということは、箱に区別がつく状態から考えると、
（０，０，１）と（０，１，０）、（１，０，０）は同じと見る、ということです。
上のように２つが同じで、１つが異なる場合は３通りずつあり、
すべてが異なる場合は３！＝６通りずつあり、
すべて同じ場合は１通りしかないことから考えていきます。


n=6m-5のとき
　３つの箱に区別があるとすると(6m-3)(6m-4)/2=18m^2-21m+6 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-5 より、2a=6m-5-c この等式を満たす整数cは、c=1,3,5,…,6m-5 の3m-2通り
　実際にはcでなくてもよいから、9m-6通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、3m-2+(18m^2-21m+6-9m+6)/6=3m^2-2m 通り

n=6m-4のとき
　３つの箱に区別があるとすると(6m-3)(6m-2)/2=18m^2-15m+3 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-4 より、2a=6m-2-c この等式を満たす整数cは、c=0,2,4,…,6m-4 の3m-1通り
　実際にはcでなくてもよいから、9m-3通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、3m-1+(18m^2-15m+3-9m+3)/6=3m^2-m 通り

n=6m-3のとき
　３つの箱に区別があるとすると(6m-2)(6m-1)/2=18m^2-9m+1 通り
　a=b=cとなる１通りを除くと18m^2-9m 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-3 より、2a=6m-3-c この等式を満たす整数cは、c=1,3,5,…,6m-3 の3m-1通り
　実際にはcでなくてもよいから、9m-3通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、1+(3m-1)+(18m^2-15m+3-9m-3)/6=3m^2-m 通り

n=6m-2 のとき
　３つの箱に区別があるとすると(6m-1)*6m/2=18m^2-3m 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-2 より、2a=6m-2-c この等式を満たす整数cは、c=0,2,4,,…,6m-2 の3m通り
　実際にはcでなくてもよいから、9m通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、3m+(18m^2-3m-9m)/6=3m^2-m 通り

n=6m-1　のとき
　３つの箱に区別があるとすると3m(6m+1)=18m^2+3m 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m-1 より、2a=6m-1-c この等式を満たす整数cは、c=1,3,5,…,6m-1 の3m通り
　実際にはcでなくてもよいから、9m通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、3m+(18m^2+3m-9m)/6=3m^2+2m 通り

n=6mのとき
　３つの箱に区別があるとすると(6m+2)(6m+1)/2=18m^2+9m+1 通り
a=b=cとなる１通りを除くと18m^2+9m 通り
　このうち、a=b≠c となるものを考えると、
　2a+c=6m より、2a=6m-c この等式を満たす整数cは、c=0,2,4,…,6m の3m+1通り
　しかし、この中には2m番目にa=b=cとなるものが含まれるので、3m通り。
　実際にはcでなくてもよいから、9m通りある。
　残りはa,b,cがすべて異なる場合だから、これを６で割ればよい。
　よって、1+(3m-1)+(18m^2+9m-9m)/6=3m^2+3m 通り

以上です。眠れなかったから頭が働いていたというわけではないので、
計算が違ったらごめんなさい。でも考え方は自信ありです。

No.3 回答者： noname#598 回答日時： 2001/06/25 01:46

ちなみに「箱のみ区別あり」は、ｘ＋ｙ＋ｚ＝ｎの、負でない整数の組合わせだから、「区切りを、その両端までゆるしたｎ＋２個から、２個選ぶ組合せ」で、

(n+2)Ｃ2=(n+2)(n+1)/2　です。

箱にも区別がつかない場合について・・・
一般には、ａ＋ｂ＋ｃ＝ｎ　かつａ≧ｂ≧ｃ　となるａ，ｂ，ｃの組合せを数えればよい。


こんがらがるので、まずは箱を２つにしてみます。つまり、
ａ＋ｂ＝ｎ　かつａ≧ｂ　となるａ，ｂの組合せについて
n=2k+1のとき、負でない整数ａ，ｂの和がｎとなる組合せ（ａ＜ｂも許す）は
(2k+1+1)Ｃ1＝2k+2個あり、ａ＝ｂとなることはないので、k+1個…★
n=2k のとき、負でない整数ａ，ｂの和がｎとなる組合せ（ａ＜ｂも許す）は
(2k+1)Ｃ1＝2k+1個あり、ａ＝ｂとなるものが１つ存在するので、
ａ＋ｂ＝ｎ　かつａ≧ｂ　となるａ，ｂの組合せはｋ+1個…★★
まとめると、

ｎ＝２ｋのとき、k+1個
ｎ＝２ｋ＋１のとき、ｋ+1個　（ｋ＝0，1，2，3，…）
よって、[ｘ]を、ｘを超えない最大の整数として表すことにすると、
箱が２個のときは　[n/2]+1　通り

箱が３つの状態はこの方法だと６通りの場合わけが発生しそう。
ずっと考えていましたが炸裂中なので、とりあえずここまでにします。
もっといい方法を知っている人がいたらお願いします（笑）

No.2 回答者： a-kuma 回答日時： 2001/06/24 18:24

> よく考えてみると、同じ個数ずつ複数の箱に入った場合が重複になるんです

そうですか？

例えば ｎ＝７ として、箱の区別があるときは １、２、４ が６通りあるのは
ＯＫですよね。で、同じ個数ずつ複数の箱に入ったとき １、３、３ も６通り
ありますよね。１、３(a)、３(b) と書けばはっきりしますか？


＃ いや、先の回答で「自信なし」にしたのは、このあたりがあるんですけどね　(^^;

この回答への補足

箱への入れ方なので、ボールを入れた箱ａｂｃを一列に並べるのではないんです。説明不足ですいません。
ちなみに、「箱のみ区別アリ」は、『ボールを一列に並べて、その間（両端も含む）にしきりを２本入れて、左から箱abcに入れるとする。しきりが「間」ひとつにつき一本しか入らないとき（ｂ≠０）はn+1Ｃ2通り、「間」一つに必ず２本はいる場合（ｂ＝０）はn+1通りなので、合計で(n+1)(n+2)/2通り』となったのですが、いかがでしょう。

補足日時：2001/06/24 21:57

No.1 回答者： a-kuma 回答日時： 2001/06/24 17:09

「箱のみ区別アリ」が解けたのであれば、その組合わせ数を箱の区別の数

3P3＝6 で割った数値が、その答えになります。

＃ いや、答えになると思います　(^^;

この回答への補足

…とは私も考えたんですが、よく考えてみると、同じ個数ずつ複数の箱に入った場合が重複になるんです。ここの解決方法がわかりません。

補足日時：2001/06/24 17:57