２項係数,スターリング数,分割数
前項で、n個の球をm個の箱に分ける方法の数として出てきた、２項係数、スターリング数、分割数の値を計算してみる。なお、ここの計算は「数え上げ理論」(野崎昭弘)によっている。
◇
(1)２項係数(binomial coefficient)
n+1個の同種の球をm+1個の異なる箱に入れる方法の数というより、異なるn個からm個を選ぶ方法の数といった方がわかりやすく
と閉じた式で書けるが、値の計算には漸化式を使った方が簡単で、次表のようになる。
∵第1項は、n番を必ず選ぶ場合で、1番から(n-1)番の中から残り(m-1)個を選ぶ
第2項は、n番を選ばない場合で、1番から(n-1)番の中からm個を選ぶ
|
C(n,m) |
m=0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
ΣC(n,m) |
|
n=0 |
1 |
|
|
|
|
|
|
|
|
1 |
|
1 |
1 |
1 |
|
|
|
|
|
|
|
2 |
|
2 |
1 |
2 |
1 |
|
|
|
|
|
|
4 |
|
3 |
1 |
3 |
3 |
1 |
|
|
|
|
|
8 |
|
4 |
1 |
4 |
6 |
4 |
1 |
|
|
|
|
16 |
|
5 |
1 |
5 |
10 |
10 |
5 |
1 |
|
|
|
32 |
|
6 |
1 |
6 |
15 |
20 |
15 |
6 |
1 |
|
|
64 |
|
7 |
1 |
7 |
21 |
35 |
35 |
21 |
7 |
1 |
|
128 |
|
8 |
1 |
8 |
28 |
56 |
70 |
56 |
28 |
8 |
1 |
256 |
◇◇
(2) スターリング数(Stirling number)
n個の異なる球をm個の同種の箱に分ける方法の数で、前項では2項係数の反転公式を用いて求めたが、包除原理を用いて求めることもできて
∵スターリング数はn個の異なる球をm個の同種の箱に分ける方法の数なので、m個の異なる箱に分ける方法の数Sをm!で割ったものになる。空箱があってよい条件でm個の箱に分ける方法はmnとおりだから
漸化式を使って計算すると、次表のようになる。
∵第1項は、n番の球が箱に1個だけ入っている場合で、1番から(n-1)番を他の(m-1)箱に分ける
第2項は、n番の球が他の球と同居している場合で、n番をm箱のどれかに入れて、さらに1番から(n-1)番をm箱に分ける
|
S(n,m) |
m=0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
ΣS(n,m) |
|
n=0 |
0 |
|
|
|
|
|
|
|
|
|
|
1 |
0 |
1 |
|
|
|
|
|
|
|
1 |
|
2 |
0 |
1 |
1 |
|
|
|
|
|
|
2 |
|
3 |
0 |
1 |
3 |
1 |
|
|
|
|
|
5 |
|
4 |
0 |
1 |
7 |
6 |
1 |
|
|
|
|
15 |
|
5 |
0 |
1 |
15 |
25 |
10 |
1 |
|
|
|
52 |
|
6 |
0 |
1 |
31 |
90 |
65 |
15 |
1 |
|
|
203 |
|
7 |
0 |
1 |
63 |
301 |
350 |
140 |
21 |
1 |
|
877 |
|
8 |
0 |
1 |
127 |
966 |
1701 |
1050 |
266 |
28 |
1 |
4140 |
◇◇◇
(3) 分割数(partition number)
n個の同種の球をm個の同種の箱に分ける方法の数で、閉じた式では表せないが次のような関係式になる。
∵まず1個ずつm個の箱に入れる。残った(n-m)個を1個の箱に入れる、2個の箱に入れる,...,m個の箱に入れる。
漸化式を使って計算すると、次表のようになる。
第1項は1個だけの箱がある場合で、1個をある箱に入れて、残り(n-1)個を他の(m-1)箱に分ける
第2項はどの箱にも2個以上入っている場合で、1個をある箱に入れて、さらに残り(n-1)個をm箱に分ける
|
P(n,m) |
m=0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
ΣP(n,m) |
|
n=0 |
0 |
|
|
|
|
|
|
|
|
0 |
|
1 |
0 |
1 |
|
|
|
|
|
|
|
1 |
|
2 |
0 |
1 |
1 |
|
|
|
|
|
|
2 |
|
3 |
0 |
1 |
1 |
1 |
|
|
|
|
|
3 |
|
4 |
0 |
1 |
2 |
1 |
1 |
|
|
|
|
5 |
|
5 |
0 |
1 |
2 |
2 |
1 |
1 |
|
|
|
7 |
|
6 |
0 |
1 |
3 |
3 |
2 |
1 |
1 |
|
|
11 |
|
7 |
0 |
1 |
3 |
4 |
3 |
2 |
1 |
1 |
|
15 |
|
8 |
0 |
1 |
4 |
5 |
5 |
3 |
2 |
1 |
1 |
22 |
◇◇◇◇
これら3つの数の分布を並べてみると、その差が視覚的にわかる。2項係数は真ん中(m=n/2)にピークがあるが、スターリング数や分割数のピークは低い方に偏っており、スターリング数はピークの幅が2項係数よりやや狭く、分割数はベタっと広がっている。といっても、この特徴から何か意味が読み取れるのか、わからない。
