ｒ個のボールをｎ個の箱に

質問

異なるｒ個のボールを異なるｎ個の箱に入れる方法は次の場合何通りあるか
(a)０個の箱が出来てもいい場合
(b)０個の箱が出来てはいけない場合
という問題なんですが
コンビネーションを使って掛け合わせるといいと思うのですが良くわかりません。
お願いします

回答No.14

graphaffine

(a)は既に回答が出ているので、(b)の方針を
書きます。
ボールを区別し、箱を区別しない場合、
このとき、ｒ個のボールをｎ個の空でない部分集合に分割する問題（所謂集合分割問題）になります。
その個数をSP(r,n)と書くと、質問の回答は箱も区別しますからSP(r,n)*n!になります。
従って、SP(r,n)がどうなるかが問題ですが、これ以降は
貴兄のレベルが分からないとどこまでかみ砕いて書いたら良いか分かりません。

全く反応が無いようですが、今までの回答はどこまで理解しているのですか。

回答No.13

kony0

#8,#10の続き。

k>nのときG_k(n)=0, k=nのときG_k(n)=1
G_k(n)=-Σ(i=k～n-1)nCi*G_k(i)

これらからn≧kのときG_k(n)=(-1)^(n-k)*nCkを数学的帰納法で導く。

n=kのときは明らか。

k≦m≦n-1のとき、G_k(m)=(-1)^(m-k)*mCkが成立していると仮定する。
G_k(n)=-Σ(i=k～n-1)nCi*G_k(i)
=-Σ(i=k～n-1)(-1)^(i-k)*nCi*iCk
=-nCk*Σ(i=k～n-1)(-1)^(i-k)*(n-k)C(i-k)
i-k=I, n-k=Nとおくと、
Σ(i=k～n-1)(-1)^(i-k)*(n-k)C(i-k)
=Σ(I=0～N-1)(-1)^I*NCI
=Σ(I=0～N)(-1)^I*NCI - (-1)^N
=(1+(-1))^N-(-1)^N
=-(-1)^(n-k)
したがって、
G_k(n)=-nCk*{-(-1)^(n-k)}=(-1)^(n-k)nCk
となり、m=nのときにも、G_k(m)=(-1)^(m-k)*mCkが成立することが言える。

したがって、n≧kのときG_k(n)=(-1)^(n-k)*nCkが示せた。

ふ～示せた。#8,#10も含めて、間違いがあれば指摘してください。自分的に納得。（笑）

回答No.12

arukamun

No.11の訂正

(a)は重複順列
　nΠr = n^r

でした。

回答No.11

arukamun

(a)は重複順列
　rΠn = r^n
（なんかrとnが逆で変ですが・・・。）

(b)はすべての箱にボールを１個ずついれた状態にしてから考えれば良いんじゃないかと思っています。
もう少し考えねば・・・。

参考URL：

http://www.geocities.co.jp/Playtown-Toys/2593/JavaScript/fact.html

回答No.10

kony0

使用するのは、#7さんも立てられた漸化式で、求める場合の数をF(n)とおくと（rは定数扱い）
F(1)=1, F(n)=n^r - Σ(i=1～n-1)nCi*F(i)
とあらわせます。

F(n)=Σ(k=1～n)G_k(n)k^rとおきます。
k>nのときG_k(n)=0
k=nのときG_k(n)=1
は明らか。
G_k(n)=-Σ(i=k～n-1)nCi*G_k(i)
あとはこれがG_k(n)=(-1)^(n-k)nCkとなることを示せばよいのですが・・・帰納的に数値を導くのは無茶な話ではないのですが、式で示すのは、帰納法を使おうとしてもなかなか思いつきません。^^;

とりあえず途中経過まで。

回答No.9

noname#24477

＃１です。
私が＃１でした回答だと（ｂ）では同じものを数えてしまうようですね。失礼しました。
もう少し考えて見ます。
とりあえずお詫びまで。

回答No.8

kony0

わたしも気になっています。(b)はかなり難問ですね。
ｒ＝４、ｎ＝３のときは、
２つのボールが入る箱の選び方・・・３通り
その箱に入れる２つのボールの選び方・・・4C2通り
残り２つの箱に２つのボールを入れる・・・２通り
⇒３×4C2×２＝36通り

とりあえず答えは
Σ(k=1～n){(-1)^(n-k) * nCk * k^r}
だと思います。考え方の整理はこれから・・・

回答No.7

mikelucky

ちょっと気になったので書き込んでみます。

r個のボールは全部入れる必要があると思います。
(a)についてはNo.1の方が書いておられる通りかと思います。
すなわち、

A,B,C...(n個)の箱に1,2,3...(r個)のボールを入れるのだから、
1のボールに対しA,B,C...のn通り、
2のボールに対しA,B,C...のn通り、
.
.
.
rのボールに対しｎ通り
で　n*n*.....*n=n^r

(b)についてはもっと複雑なように思います。
例えば、箱が2個、ボールが3個のとき、入れ方は6通り
です(他の方の回答だとそうはならない気がします)

ボールがr個のとき
例えば箱が1個なら、1通り

箱が2個なら
入れ方は2^rで、どちらかが空箱になるときを除くので

2^r- 2C1*1

箱が3個なら

入れ方は3^rで、2個の空ができるとき、その選び方は
3C2
1個の空箱ができるときは空の箱の選び方が3C1で、
残りの箱は2つとも空であってはいけないので(2個が空のときと重複するから)、箱が2個だったときの答えを用いて2^r- 2C1*1

よって
3^r -3C1 *(2^r- 2C1*1) -3C2*1

これを続けていくと
箱がk個で空箱ができない場合の数を、F(k)とするなら、箱がn個の場合
F(n)=n^r- nC1*F(n-1)- nC2*F(n-2)-...-nCn-1*F(1)

となるかと思います。

と、ここまでは考えたのですが、この漸化式(?
)を解く術を知りません。
ごめんなさい。

もっとスマートな方法があるきもしますが...。

回答No.6

marutyon

異なるボール＆箱でした。ごめんなさい。見えてませんでした。

と、いうことは…

(a)は、みなさんの言うとおり。r^n
(b)は…

もう少し考えて見ます。

回答No.5

yuusukekyouju

>異なるｒ個のボールを異なるｎ個の箱
つまりボールも箱も区別するということですね。
(a)はひとつのボールについてｎとおりの選択肢があるので
n^ｒ

(ｂ)たとえばボールを４個（1.2.3.4）、箱を２個（1.2）と考えた場合
１の箱に3個はいるのは次の４通り
1.2.3　1.2.4　1.3.4　2.3.4

１の箱に2個はいるのは次の6通り
1.2　1.3　1.4　2.3　2.4　3.4

１の箱に1個はいるのは次の４通り
1　2　3　4　

つまり全部で4+6+4＝14通り
ほかの回答者の計算ではこの答えにならないのではないでしょうか。

現在回答を考えています。
わかれば回答します。