-PR-
解決済み

何通り?

  • 困ってます
  • 質問No.94892
  • 閲覧数202
  • ありがとう数1
  • 気になる数0
  • 回答数8
  • コメント数0

お礼率 21% (7/32)

どこかの大学の入試問題だったらしいんですが…
「区別のつかないn個のボールを、区別のつかない3つの箱に入れるとき、その入れ方は何通り?」
ボールも箱も区別アリ、ボールのみ区別アリ、箱のみ区別アリ、の三問は解けたんですが、最後のこの問題が解けません。誰か教えて下さい。
通報する
  • 回答数8
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.6

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

きれいになったのできっと正しいと思います(笑)
お礼コメント
ikeshi

お礼率 21% (7/32)

なるほど納得です。細かい場合分けが必要になるんですね。詳しい回答ありがとうございました。もし、もっと楽な解法を発見したらまたお願いします。
投稿日時 - 2001-06-25 18:56:57
-PR-
-PR-

その他の回答 (全7件)

  • 回答No.2
レベル14

ベストアンサー率 50% (1122/2211)

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

そうですか?

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


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

お礼率 21% (7/32)

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


  • 回答No.1
レベル14

ベストアンサー率 50% (1122/2211)

「箱のみ区別アリ」が解けたのであれば、その組合わせ数を箱の区別の数
3P3=6 で割った数値が、その答えになります。

# いや、答えになると思います (^^;
補足コメント
ikeshi

お礼率 21% (7/32)

…とは私も考えたんですが、よく考えてみると、同じ個数ずつ複数の箱に入った場合が重複になるんです。ここの解決方法がわかりません。
投稿日時 - 2001-06-24 17:57:41
  • 回答No.3

ちなみに「箱のみ区別あり」は、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通りの場合わけが発生しそう。
ずっと考えていましたが炸裂中なので、とりあえずここまでにします。
もっといい方法を知っている人がいたらお願いします(笑)
  • 回答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でなくてもよいから、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 通り

以上です。眠れなかったから頭が働いていたというわけではないので、
計算が違ったらごめんなさい。でも考え方は自信ありです。
  • 回答No.7
レベル10

ベストアンサー率 30% (25/81)

たびたびすみません。下の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) )

(誰かこの後の展開やり方教えて。)
補足コメント
ikeshi

お礼率 21% (7/32)

展開…わかんないですねぇ。
でも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:32
  • 回答No.5
レベル10

ベストアンサー率 30% (25/81)

間違っていたらごめんなさい。考えてみたことを投稿します。私にとって簡単と感じられた(思いっきり勘違いでなければ!)順番に、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を展開したものが答えになると思うのですが(検証まだ)もっとエレガントな方法あるのでしょうねー。

取り急ぎ投稿してみました。
  • 回答No.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は、私の能力ではあれ以上考え方は簡単にできないです。悪しからず…
補足コメント
ikeshi

お礼率 21% (7/32)

すいません。タイプミスです。詳しい回答ありがとうございます。
投稿日時 - 2001-06-26 21:19:59
このQ&Aのテーマ
このQ&Aで解決しましたか?
AIエージェント「あい」

こんにちは。AIエージェントの「あい」です。
あなたの悩みに、OKWAVE 3,500万件のQ&Aを分析して最適な回答をご提案します。

関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


専門家があなたの悩みに回答!

-PR-

ピックアップ

-PR-
ページ先頭へ