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

A 回答 (8件)

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


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

1箇所に寄った場合は1通り
2箇所に寄った場合は(2^n-2)/2=2^(n-1)-1通り
3箇所全部に入っている場合は、まず箱に区別がつくとすると、
3^nから1箇所に偏った3通り、2箇所に偏った3*(2^n-2)通りを引けば良い。
(2箇所の場合に3を掛けるのは、どの箱を空にするかの選び方が3通りあるから)
3^n-3*(2^n-2)-3=3^n-3*2^n+3より、
(3^n-3*2^n+3)/6=(3^(n-1)+1)/2-2^(n-1)通り

以上より、
1+2^(n-1)-1+(3^(n-1)+1)/2-2^(n-1)
=(3^(n-1)+1)/2 通りです。
もちろんikeshiさんの考え方の方がスマートなことは知っていますが、厳密に解いてみました。

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

この回答への補足

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

補足日時:2001/06/26 21:19
    • good
    • 0

たびたびすみません。

下の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) )

(誰かこの後の展開やり方教えて。)

この回答への補足

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

補足日時:2001/06/25 18:44
    • good
    • 0

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



箱に区別がつかないということは、箱に区別がつく状態から考えると、
(0,0,1)と(0,1,0)、(1,0,0)は同じと見る、ということです。
上のように2つが同じで、1つが異なる場合は3通りずつあり、
すべてが異なる場合は3!=6通りずつあり、
すべて同じ場合は1通りしかないことから考えていきます。

n=6m-5のとき
 3つの箱に区別があるとすると(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がすべて異なる場合だから、これを6で割ればよい。
 よって、3m-2+(18m^2-21m+6-9m+6)/6=3m^2-2m 通り

n=6m-4のとき
 3つの箱に区別があるとすると(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がすべて異なる場合だから、これを6で割ればよい。
 よって、3m-1+(18m^2-15m+3-9m+3)/6=3m^2-m 通り

n=6m-3のとき
 3つの箱に区別があるとすると(6m-2)(6m-1)/2=18m^2-9m+1 通り
 a=b=cとなる1通りを除くと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がすべて異なる場合だから、これを6で割ればよい。
 よって、1+(3m-2)+(18m^2-9m-9m+6)/6=3m^2 通り

n=6m-2 のとき
 3つの箱に区別があるとすると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がすべて異なる場合だから、これを6で割ればよい。
 よって、3m+(18m^2-3m-9m)/6=3m^2+m 通り

n=6m-1 のとき
 3つの箱に区別があるとすると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がすべて異なる場合だから、これを6で割ればよい。
 よって、3m+(18m^2+3m-9m)/6=3m^2+2m 通り

n=6mのとき
 3つの箱に区別があるとすると(6m+2)(6m+1)/2=18m^2+9m+1 通り
a=b=cとなる1通りを除くと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がすべて異なる場合だから、これを6で割ればよい。
 よって、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

きれいになったのできっと正しいと思います(笑)
    • good
    • 0
この回答へのお礼

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

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

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

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

【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個の非個性なボールの並びに対して、左側のボールの数が右側のボールの数よりも小さくならないように仕切りを1つ入れる入れ方、の場合の数" とする。
[ ]はガウス記号とする([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を展開したものが答えになると思うのですが(検証まだ)もっとエレガントな方法あるのでしょうねー。

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

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


途中違ったらごめんなさい。
箱に区別がつかないということは、箱に区別がつく状態から考えると、
(0,0,1)と(0,1,0)、(1,0,0)は同じと見る、ということです。
上のように2つが同じで、1つが異なる場合は3通りずつあり、
すべてが異なる場合は3!=6通りずつあり、
すべて同じ場合は1通りしかないことから考えていきます。


n=6m-5のとき
 3つの箱に区別があるとすると(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がすべて異なる場合だから、これを6で割ればよい。
 よって、3m-2+(18m^2-21m+6-9m+6)/6=3m^2-2m 通り

n=6m-4のとき
 3つの箱に区別があるとすると(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がすべて異なる場合だから、これを6で割ればよい。
 よって、3m-1+(18m^2-15m+3-9m+3)/6=3m^2-m 通り

n=6m-3のとき
 3つの箱に区別があるとすると(6m-2)(6m-1)/2=18m^2-9m+1 通り
 a=b=cとなる1通りを除くと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がすべて異なる場合だから、これを6で割ればよい。
 よって、1+(3m-1)+(18m^2-15m+3-9m-3)/6=3m^2-m 通り

n=6m-2 のとき
 3つの箱に区別があるとすると(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がすべて異なる場合だから、これを6で割ればよい。
 よって、3m+(18m^2-3m-9m)/6=3m^2-m 通り

n=6m-1 のとき
 3つの箱に区別があるとすると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がすべて異なる場合だから、これを6で割ればよい。
 よって、3m+(18m^2+3m-9m)/6=3m^2+2m 通り

n=6mのとき
 3つの箱に区別があるとすると(6m+2)(6m+1)/2=18m^2+9m+1 通り
a=b=cとなる1通りを除くと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がすべて異なる場合だから、これを6で割ればよい。
 よって、1+(3m-1)+(18m^2+9m-9m)/6=3m^2+3m 通り

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

ちなみに「箱のみ区別あり」は、x+y+z=nの、負でない整数の組合わせだから、「区切りを、その両端までゆるしたn+2個から、2個選ぶ組合せ」で、


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

箱にも区別がつかない場合について・・・
一般には、a+b+c=n かつa≧b≧c となるa,b,cの組合せを数えればよい。


こんがらがるので、まずは箱を2つにしてみます。つまり、
a+b=n かつa≧b となるa,bの組合せについて
n=2k+1のとき、負でない整数a,bの和がnとなる組合せ(a<bも許す)は
(2k+1+1)C1=2k+2個あり、a=bとなることはないので、k+1個…★
n=2k のとき、負でない整数a,bの和がnとなる組合せ(a<bも許す)は
(2k+1)C1=2k+1個あり、a=bとなるものが1つ存在するので、
a+b=n かつa≧b となるa,bの組合せはk+1個…★★
まとめると、

n=2kのとき、k+1個
n=2k+1のとき、k+1個 (k=0,1,2,3,…)
よって、[x]を、xを超えない最大の整数として表すことにすると、
箱が2個のときは [n/2]+1 通り

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

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



そうですか?

例えば n=7 として、箱の区別があるときは 1、2、4 が6通りあるのは
OKですよね。で、同じ個数ずつ複数の箱に入ったとき 1、3、3 も6通り
ありますよね。1、3(a)、3(b) と書けばはっきりしますか?


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

この回答への補足

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

補足日時:2001/06/24 21:57
    • good
    • 0

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


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

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

この回答への補足

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

補足日時:2001/06/24 17:57
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ