オンライン健康相談、gooドクター

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

gooドクター

A 回答 (14件中1~10件)

(a)は既に回答が出ているので、(b)の方針を


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

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

#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も含めて、間違いがあれば指摘してください。自分的に納得。(笑)
    • good
    • 0

No.11の訂正



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

でした。
    • good
    • 1

(a)は重複順列


 rΠn = r^n
(なんかrとnが逆で変ですが・・・。)

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

参考URL:http://www.geocities.co.jp/Playtown-Toys/2593/Ja …
    • good
    • 0

使用するのは、#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となることを示せばよいのですが・・・帰納的に数値を導くのは無茶な話ではないのですが、式で示すのは、帰納法を使おうとしてもなかなか思いつきません。^^;

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

#1です。


私が#1でした回答だと(b)では同じものを数えてしまうようですね。失礼しました。
もう少し考えて見ます。
とりあえずお詫びまで。
    • good
    • 0

わたしも気になっています。

(b)はかなり難問ですね。
r=4、n=3のときは、
2つのボールが入る箱の選び方・・・3通り
その箱に入れる2つのボールの選び方・・・4C2通り
残り2つの箱に2つのボールを入れる・・・2通り
⇒3×4C2×2=36通り

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

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



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=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)

となるかと思います。

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

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

異なるボール&箱でした。

ごめんなさい。見えてませんでした。

と、いうことは…

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

もう少し考えて見ます。
    • good
    • 0

>異なるr個のボールを異なるn個の箱


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

(b)たとえばボールを4個(1.2.3.4)、箱を2個(1.2)と考えた場合
1の箱に3個はいるのは次の4通り
1.2.3 1.2.4 1.3.4 2.3.4

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

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

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

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

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


人気Q&Aランキング