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

[←]　[↑]　[→]

---

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

◇

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

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

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

(c) 空箱が、ない(n≧m)/あってよい

結論を先に示すと

No	球(n個)	箱(m個)	空箱	方法の数	説明
1	異なる	異なる	なし(n≧m)	m! S(n,m)	スターリング数に箱の並べ方m!をかける
2	異なる	異なる	あってよい	m^n	球n個それぞれに箱を割り当てる方法の数(重複順列)
3	異なる	同じ	なし(n≧m)	S(n,m)	スターリング数
4	異なる	同じ	あってよい	Σk=1..m S(n,k)	スターリング数の和
5	同じ	異なる	なし(n≧m)	n-1Cm-1	球の間n-1箇所に仕切りm-1個を入れる方法の数
6	同じ	異なる	あってよい	n+m-1Cm-1	球n個と仕切りm-1個を並べる方法の数(重複組合せ)
7	同じ	同じ	なし(n≧m)	P(n,m)	分割数
8	同じ	同じ	あってよい	P(n+m,m)	まず球m個を1個ずつ入れておいて残りn個を空箱ありで入れる

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

◇◇

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

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

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

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

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

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

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

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

とスターリング数の閉じた式が求まる。

◇◇◇

球が同種のときは、空箱があってよい条件での数Y(n,m)は空箱がない条件下の数X(n+m,m)と等しい。なぜならX(n+m,m)は、まず球を1個ずつm個の箱に入れておいて残りn個を空箱ありで分ける方法の数Y(n,m)と等しい。

例3）球が同種、箱が同種のとき(No.7とNo.8)

---

[←]　[↑]　[→]