n個の球をm個の箱に分ける方法

[] [] []


校のとき確率や場合の数の問題が全くできなかったが、理論を知らなかったことが大きいように思う。最近、「数え上げ理論」(野崎昭弘)という本を読んですこし理論を知ったので、典型的な問題:n個の球をm個の箱に分ける方法を整理してみた。

この問題は次の前提条件をはっきりさせないと混乱する。

(a) 球の種類が、異なる/同じ

(b) 箱の種類が、異なる/同じ

(c) 空箱が、ない(nm)/あってよい

結論を先に示すと

No.

(n)

(m)

空箱

方法の数

説明

1

異なる

異なる

なし(nm)

nSm*m!

スターリング数に箱の並べ方m!をかける

2

異なる

異なる

あってよい

mn

n個それぞれに箱の番号1からmをふる方法の数(重複順列)

3

異なる

同じ

なし(nm)

nSm

スターリング数

4

異なる

同じ

あってよい

Σk=1..m nSk

スターリング数の和

5

同じ

異なる

なし(nm)

n-1Cm-1

球の間n-1箇所に仕切りm-1個を入れる方法の数

6

同じ

異なる

あってよい

n+m-1Cm-1

n個と仕切りm-1個を並べる方法の数(重複組合せ)

7

同じ

同じ

なし(nm)

P(n,m)

分割数

8

同じ

同じ

あってよい

Σk=1..m P(n,k)

分割数の和

この表No.2,5,6の場合はべき乗や2項係数nCmで表せるが、その他の場合は少し複雑でスターリング数とか分割数という名前が付けられている数になる。これらについては次項以降で詳しく見る。

一般に、空箱があってよい条件での数Y(n,m)は空箱がない条件下の数X(n,m)を使って表せるすなわち空でない箱が1個からm個ある場合に分けて、それらを合計すればY(n,m)になるので

箱の種類が同じ条件下では

箱の種類が異なる条件下では

ここで2項係数の反転公式を適用すると逆にXYで表せる。(補足-2項係数の反転公式)

1)球が同種、箱が異種のとき(No.5No.6)

∵左辺=(1+x)n+m-1xm-1の係数、右辺=(1+x)mxm-kの係数 と(1+x)n-1xk-1の係数との積

2)球が異種、箱が異種のとき(No.1No.2)

したがって2項係数の反転公式を適用すると

とスターリング数が求まる。


[] [] []