- 締切済み
有名な「n人を空部屋なく3部屋に分けろ」問題。じゃあ4部屋以上のときは？
受験直前の知識整理をしていて思ったことです。 「n人を区別のない3部屋にわける方法は何通りあるか。ただし1人もいない部屋があってはならない」 ・・・という問題は受験数学を勉強した人は多分皆解いたことがあると思います。 プロセスとしては、区別されるｘ個の部屋のうちy個(x > y)の部屋のみが 空となる場合の数をM(x,y)として、 （分かりにくいですが、あとの議論のためにわざと関数的に書きました） 2部屋だけが空となる場合の数を求める → M(3,2) = 3 1部屋だけが空となる場合の数を求める → M(3,1) = C[3,2]*M(2,0) = 3*(2^n - M(2,1)) = 3*(2^n - 2) 求める場合の数は → M(3,0) = 3^n - M(3,2) - M(3,1) = 3^n - 3*(2^n) +3 部屋は区別されないので3!で割る ・・・ところでこれ、4部屋以上になった場合はどうなるのでしょうか。 たとえば4部屋の場合、以下は自分が考えた解答ですが （あってるかどうか分かりませんが、最終的にn=4でちゃんと1になるので大丈夫なはず・・・） M(4,3) = 4 M(4,2) = C[4,2]*M(2,0) = 6*(2^n - 2) ←（M(2,0)は上記から） M(4,1) = C[4,3]*M(3,0) = 4*(3^n - 3*(2^n) +3) ←（M(3,0)は上記から） M(4,0) = 4^n - M(4,3) - M(4,2) - M(4,1) = 4^n - 4*(3^n) + 6*(2^n) - 4 部屋は区別されないので4!で割る しかしこれ、合っているとしてもものすごくやり方が泥臭い気がする上に、 部屋の数がm個などと一般化されたら手も足も出なくなります。 この問題はもっと綺麗な方法で一般化して解くことはできないのでしょうか。
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- aiueo95240
- ベストアンサー率39% (15/38)
関連するQ&A
- 5-8 高校数学 場合の数
nを正の整数とし,n個のボールを3つの箱に分けて入れる問題を考える、ただし1個のボールも入らない箱があってもよいとする 以下に述べる4つの場合について、それぞれ相異なる入れ方の総数を求めたい (1)1からnまで異なる番号のついたn個のボールをA,B,Cと区別された3つの箱に入れる場合その入れ方は何通りあるか (2)互いに区別のつかないn個のボールをA,B,Cと区別された3つの箱に入れる場合その入れ方は何通りあるか (3)１からnまで異なる番号のついたn個のボールを区別のつかない3つの箱に入れる場合その入れ方は全部で何通りあるか (4)nが6の倍数6mであるときn個の互いに区別のつかないボールを区別のつかない3つの箱に入れる場合その入れ方は何通りあるか 解説(1)は3^n通り (2)は[n+2]C[2]=(n^2+3n+2)/2通り (3)求める場合の数を次のように三分割する n個とも1箱だけにいれるもの・・・ｘ通り n個を2箱に分散して入れるもの・・y通り n個を3箱に分散して入れるもの・・・z通り これらx,y,zと(1)との関係を考えると、まずx=1であり(1)ではこれを3通りと数えy通りの1つ1つを(1)では 3!通りと数えz通りの1つ１つを(1)では3!通りと数えている したがって x×3+(y+z)×6=3^nよって求める場合の数x+y+zは1+y+z=1+(3^n-1×3)/6={3^(n-1)+1}/2通り (4)3箱のボールの個数をa,b,c(a<=b<=c)としa=b=cをみたすもの・・p通り a=b<c or a<b=cをみたすもの・・q通り a<b<cをみたすもの・・r通り すると(2)の場合の数はp+3q+6r通りと数えられるからp+3q+6r=(n^2+3n+2)/2・・・(2) ここでp=1であり、またq通りは(0,0,6m),(1,1,6m-2),・・・、(3m,3m,0)の3m+1通りから(2m,2m,2m)の1通り を除いてq=3mである よって(2)からr=1/6×{(36m^2+18m+2)-(1+3×3m)}=3m^2 以上により答えはp+q+r=3m^2+3m+1通り とあるのですが (3)のx,y,zが(1)で1や3!通りずつという所と x×3+(y+z)×6=3^n の所が何を意味しているのか分かりません (4)の解説で(2)の場合の数がp+3q+6rの所とr=1/6{}=3m^2 以上によりp+q+r=3m^2+3m+1通りというのが何でなのか分かりません
- ベストアンサー
- 数学・算数
- 5-8 高校数学 場合の数
nを正の整数とし、n個のボールを3つの箱に分けて入れる問題を考える ただし1個のボールも入らない箱があってもよいものとする 以下に述べる4つの場合についてそれぞれ相異なる入とれ方の総数を求めたい (1)1からnまで異なる番号の付いたn個のボールをA,B,Cと区別された3つの箱に入れる場合、その入れ方は全部で何通りあるか (2)互いに区別の付かないn個のボールをA,B,Cと区別された3つの箱に入れる場合その入れ方は全部で何通りあるか (3)1からnまで異なる番号の付いたn個のボールを区別の付かない3つの箱に入れる場合、その入れ方は全部で何通りあるか (4)nが6の倍数6mであるとき、n個の互いに区別の付かないボールを区別の付かない3つの箱に入れる場合、その入れ方は全部で何通りあるか (解説) (1)3^n (2)A,B,Cにそれぞれa,b,c個入るとしてa+b+c=n(a>=0,b>=0,c>=0)(1) をみたす整数解(a,b,c)の個数を求めればよいが、(1)は(a+1)+(b+1)+(c+1)=n+3 (a+1>=1,b+1>=1,c+1>=1) と同値であることに着目して[n+2]C[2]=(n^2+3n+2)/2通り (3)求める場合の数を次のように3分割する nことも1箱だけに入れるもの...x通り n個を2箱に分散して入れるもの...y通り n個を3箱に分散して入れるもの...z通り これらx,y,zと(1)との関係を考えると、まずx=1であり(1)ではこれを3通りと数えy通りの1つ1つを(1)では3!通りと数えz通りの1つ1つを(1)では3!通りと数えている したがってx×3+(y+z)×6=3^n(x=1) よって求める場合の数x+y+zは1+y+z=1+(3^n-1×3)/6=(3^(n-1)+1)/2通り (4)3箱のボールの個数をa,b,c(a<=b<=c)とし(3)と同様に求める場合の数を次のように3分割する a=b=cをみたすもの...p通り a=b<c or a<b=cをみたすもの...q通り a<b<cをみたすもの...r通り すると(2)の場合の数はp+3q+6r通りと数えられるから p+3q+6r=(n^2+3n+2)/2(2) ここでp=1であり、またq通りは(0,0,6m)(1,1,6m-2)....(3m,3m,0)の3m+1通りから(2m,2m,2m)の1通りを除いてq=3mである、よって(2)から r=1/6×{1/2×(36m^2+18m+2)-(1+3×3m)}=3m^2 以上により答えはp+q+r=3m^2+3m+1通り の (3)のx,y,zが(1)で1や3!通りずつという所と x×3+(y+z)×6=3^n の所が何を意味しているのか分かりません (4)の解説で(2)の場合の数がp+3q+6rの所とr=1/6{}=3m^2 以上によりp+q+r=3m^2+3m+1通りというのが何でなのか分かりません を質問したら (3) n個とも1箱だけにいれるもの・・・ｘ通り これが(1)の数え方なら3通りあり、(3)の形では1通り n個を2箱に分散して入れるもの・・y通り n個を3箱に分散して入れるもの・・・z通り yとzの数は同じ考え方で計算できるという意味で同じです。 例(6,2,1)(6,1,2)(1,6,2)(1,2,6)(2,6,1)(2,1,6) は全て同じものとして考えられますが、同様にして (6,3,0)(6,0,3)(0,6,3)(0,3,6)(3,6,0)(3,0,6) となりこの両者は同じものです。この両者は同じですから分けて考えるのではなく、同じものとして(y+z)を求めた方が楽 xとy,zの違いは一番多く入った箱以外の二つの箱を区別するかどうかだけです。 便宜的に箱をABCと名前をつけると、(1)の結果から3^n通あり ここからどれか一つの箱にだけ入っている場合の3通りを引くと(3^n-3)になります。この箱の名前を付け替えるとすればA→3通り、B→2通り、Cは残り、と3!通りあるはずです。 したがって、x+y+z = 1 + (3^n-3)÷3! (4) まずa=b=c の時は1通りしかないのは問題ないでしょう。このとき、a=b=c=2mです。次にa=b<c or a<b=cをみたすもの・・q通り ですが、a=bのとき、a<cなのでaは0から2m-1までの2m通り、同様にb=cのときはbは2m+1から3mまでのm通りあるはずです。 a<b<cをみたすもの・・r通り a<b<cから、aは0～2m-1までの2m通りあるはずです。aとbが決まればcも決まるという関係上、aとbだけを考えればよいです ここでaが奇数のときはm通りあり a=2m-1の時、b+c=4m+1からbは2mの1通り a=2m-3の時、b+c=4m+3からbは2m-2～2m+1の4通り ・・・ a=1の時、b+c=6m-1からbは2～3m-1の(3m-2)通り よりΣ(3m-2)=3m(m+1)/2-2m通り 偶数のときも同様にm通りあり、（b=cとなるときを除外しなければならないのに注意） a=2m-2の時、b+c=4m+2からbは2m-1～2mの2通り a=2m-4の時、b+c=4m+4からbは2m-3～2m+1の5通り ・・・ a=0の時、b+c=6mからbは1～3m-1の(3m-1)通り よりΣ(3m-1)=3m(m+1)/2-m通り よって 3m(m+1)/2-2m + 3m(m+1)/2-m と回答して下さったのですが (3)でyとzが同じとあるのですが例えばn=6の時 箱が空の時(3,3,0),(3,0,3),(0,3,3)とあり箱に入る球がすべて違うとき(1,2,3)(1,3,2)(2,1,3)(2,3,1)(3,1,2)(3,2,1)となり異なるのではないですか？同じと言うのが何故同じなのか分かりません 仮に(y+z)を求めるとして、 (3^n-3)になるのも分からないです (4)は偶数と奇数で分ける所ですが偶数だとb=cの場合があるから分ける必要があるとあるのですがb=cになると何故駄目なのでしょうか？
- ベストアンサー
- 数学・算数
- 数学の順列・組合せの問題です。
数学の順列・組合せの問題です。 N個の箱にn個の玉を入れる場合の数を求めよ（箱は区別でき、玉を無制限に入れられるとする）、という問題で １ 玉も区別できるときの場合の数は？ ２ 玉が区別できないときの場合の数は？ ３ 箱に１つまでしか玉を入れられないときの場合の数は？（玉は区別できない） １の答えがN＾ｎ通りしかわからないのでよろしくおねがいします
- ベストアンサー
- 数学・算数
- 不等式の問題がわかりません
（１） 2x+3y≦6n, x≧0, y≧0 （aは正の整数） を満たす点P（x,y）で、x,yがどちらも整数であるもの（格子点）の個数を求めよ。 （２） 2x+3y+6z≦6n, x≧0, y≧0 z≧0 （aは正の整数） を満たす点P（x,y,z）で、x,y,zがすべて整数であるもの（格子点）の個数を求めよ。 という問題で、 (1)は不等式を図示して y=k（k=1,2・・・）とy=-(2/3)x+2n の交点は（ 3n-(3/2)k , k ） 交点が整数であるために2k=mとおくと、 y=m上の格子点の数は 3n-3m+1 よって、1≦y≦2nにおいて、y=（偶数）上の格子点の数は Σ[m=1,n]（3n-3m+1） ＝（3/2）n^2-（1/2）n また図から、y=2k-1上の格子点の数は y=2k=m上の格子点の数より1多いので、 1≦y≦2nにおいて、y=（奇数）上の格子点の数は Σ[m=1,n]｛3n-3m+2｝ ＝（3/2）n^2+（1/2）n y=0上の格子点の数は3n+1より、 求める値は （3/2）n^2-（1/2）n＋（3/2）n^2+（1/2）n+3n+1 ＝3n^2+3n+1 ここまでは分かりました。 （２）はどうやっていいか手の付け方も分かりません。 (1)を使って簡単にして解くような気はします（分かりませんが）。 分かる方お願いします。
- ベストアンサー
- 数学・算数
- x^n+y^n=1以外でn=2のとき円を表す関数の種類
x^n+y^n=1 以外にも(x+y)^n+(x-y)^n=1や (x+y)^n+(y-x)^n=1はｎが２のときに円を表しますが、それ以外の数ではグラフの形が違うようです(回転している？）。このようにｎが２のときに円を表す関数というのは他にも無数に作れるのでしょうか。
- ベストアンサー
- 数学・算数
- 高校数学の場合の数の問題です。
nを自然数とする、n個のボールを３つの箱に分けて入れる。次のように入れる入れ方は何通りあるか。ただし、一個のボールも入らない箱があっても良いものとする。 (1)１からnまで異なる番号のついたn個のボールを、A、B、Cと区別された３つの箱に入れる (2)互いに区別のつかないn個のボールを、A、B、Cと区別された３つの箱に入れる (3)１からnまで異なる番号のついたn個のボールを、区別のつかない３つの箱に入れる やり方も含めて教えていただけると助かりますm(__)m
- ベストアンサー
- 数学・算数
- にゃんこ先生の自作問題、n^2の最高位の数字が1である確率は？
にゃんこ先生といいます。 nは自然数として、 n^2の最高位の数字が1ににゃる確率 を知りたいのですが、具体的に定まるのでしょうか? 10^(2m)≦n^2＜2*10^(2m) のとき、 10^m≦n＜(√2)×10^m 10^m≦n＜(1.414)×10^m この中でn^2の最高位の数字が1ににゃる個数は、 約0.414×10^m 個 10^(2m+1)≦n^2＜2*10^(2m+1) のとき、 (√10)×10^m≦n＜(√20)×10^m (3.162)×10^m≦n＜(4.472)×10^m この中でn^2の最高位の数字が1ににゃる個数は、 約1.310×10^m 個 以上のところまではご教授いただけたのですが。
- ベストアンサー
- 数学・算数
- 第二種スターリング数の母関数の組合せ論・計数子による解釈
1,2,3,…,nのn個の数字を、k種類の区別のないグループに分ける場合の数を、第二種スターリング数と言って、ここでは、S(n,k) と書きます。 すると、1,2,3,…,nのn個の数字を、k種類の区別のあるグループに分ける場合の数は、k!*S(n,k) となります。 これは、f:{1,2,…,n}→{1,2,…,k}の全射の場合の数でもあります。 ところで、 Σ[n=0,∞] k!*S(n,k)x^n/n! = (e^x - 1)^k という公式があります。 右辺のx^n/n!の係数は、1,2,…,kの数字を重複を許してn個並べて、全種類の数字が少なくとも1回は使われているという条件をつけたときの場合の数とみなせます。（指数型計数子） ここまではいいのですが、似たような公式 Σ[n=0,∞] S(n,k)x^n = x^k/(1-x)(1-2x)…(1-kx) を計数子によって解釈する方法があれば、どうか教えてください。
- ベストアンサー
- 数学・算数
補足
ちょっと検索してみたんですが、はっきり言ってまったく分かりません・・・ （というか、どう見ても高校範囲で理解できるとは思えない）。 個人的に、もしかして漸化式が必要なのかなあ・・・とかは思っていたのですが。 とりあえず、高校範囲では無理、泥臭い方法で解け。 一般化なんて難しすぎてまず受験では出てこない。 ということでいいのでしょうか？