解決済み

高校数学の場合の数・確率の問題です。解答解説お願いします。


nは2以上の自然数とする。異なるn個のボールを4つの箱に入れる方法について考える。ただし、空の箱は2つ以下とする。

①箱を区別するとき、入れ方は何通りか

②箱を区別しないとき、入れ方は何通りか


①が4^n −4通りで、②は空箱が1個以下のときと空箱が2個のときで場合分けされるところまではわかりました。その後がわかりません。解説お願いします。

ベストアンサー

ベストアンサー

 ①はたしかに 4n44^n - 4 通りとなりますね。しかし②はいささか高校で学習する範囲を超えている気がします。以下に書いたことは、私ならこう考えて解答する、という程度のことだと思って読んでください。


nn 個の区別可能なボールを mnm \leq n 個の箱へ分けて入れる仕方の数は、第2種スターリング数 SnmS_n^m として知られている。たとえば、ボール a,b,c,da,b,c,d22 個の箱へ分けて入れる仕方は

abcd, bacd, cabd, dabc, abcd, acbd, adbca|bcd,\ b|acd,\ c|abd,\ d|abc,\ ab|cd,\ ac|bd,\ ad|bc

77 通りであるから、S42=7S_4^2 = 7 である。第2種スターリング数には

Snm=1m!k=1m(1)mkmCkknS_n^m = \frac{1}{m!} \sum_{k = 1}^m (-1)^{m - k} {}_m\mathrm{C}_k k^n

という表示が知られている(この公式の導出については、たとえば下に掲げた参考文献の第3章を参照のこと)。

 さて、n2n \geq 2 個のボールを 44 個の箱へ分けて入れる仕方の数 TnT_n を考える。ちょうど 44 つに分けるならば Tn=Sn4T_n = S_n^4 であるが、空の箱があってもよいので、

Tn=Sn1+Sn2++Snmin(n,4)T_n = S_n^1 + S_n^2 + \cdots + S_n^{\min(n,4)}

である。ここで上のスターリング数の公式から

Tn=2n2+4n1+26T_n = 2^{n - 2} + \frac{4^{n - 1} + 2}{6}

となることが計算できる。ためしに計算してみると、n=3n = 3 のとき Tn=2+(16+2)/6=5T_n = 2 + (16 + 2)/6 = 5。一方、33 個のボール a,b,ca,b,c44 個の箱へ入れる仕方は

abcϕϕϕ, abcϕϕ, bacϕϕ, cabϕϕ, abcϕabc|\phi|\phi|\phi,\ a|bc|\phi|\phi,\ b|ac|\phi|\phi,\ c|ab|\phi|\phi,\ a|b|c|\phi

55 通りであり、たしかに一致する(ここで ϕ\phi は箱が空であることを表わす)。

「空の箱は 22 個以下」という条件を考えれば、条件に適わない 11 通りの場合が除外され、22つ以上の箱へボールを入れる仕方の数は

Tn1=2n2+4n146T_n - 1 = 2^{n - 2} + \frac{4^{n - 1} - 4}{6}

であると分かる」


参考:C.ベルジュ著 野崎昭弘訳『組合せ論の基礎』サイエンス社 サイエンスライブラリ数学=9


そのほかの回答(0件)

関連する質問

もっとみる