2項係数,スターリング数,分割数

[] [] []


前項でみたように、n個の球をm個に分ける方法の数として、2項係数、スターリング数、分割数というのが出てきた。この項では、これらの数を整理する。なお、ここの計算は「数え上げ理論」(野崎昭弘)によっている。

まず2項係数(binomial coefficient)n+1個の同種の球をm+1個の異なる箱に入れる方法の数で、

と閉じた式で書けるが、漸化式

を使った方が値を計算するには簡単で、次表のようになる。

C(n,m)

0

1

2

3

4

5

6

7

8

ΣC(n,m)

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

◇◇

スターリング数(Stirling number)は異なる球をm個の同種の箱に分ける方法の数で、前項では2項係数の反転公式を用いて求めたが、包除原理を用いて求めることもできて

∵スターリング数はn個の異なる球をm個の同種の箱に分ける方法の数なので、m個の異なる箱に分ける方法の数Sm!で割ったものになる。空箱があってよい条件でm個の箱に分ける方法はmnとおりだから

漸化式

∵異なn個をm組に分ける方法は次の2つの場合に分けられる

  (n-1)個を(m-1)組に分けて、残り1個を残りの組に入れる

  (n-1)個を(m)組に分けて、残り1個をm個の組のどれかに入れる

を使って計算すると、次表のようになる。

S(n,m)

0

1

2

3

4

5

6

7

8

ΣS(n,m)

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

◇◇◇

最後に分割数(partition number)は、n個の同種の球をm個の同種の箱に分ける方法の数で、閉じた式では表せないが次のような関係式になる。

∵ま1個づつm個の箱に入れる。残ったn-m個を1個の箱に入れる、2個の箱に入れる,...,m個の箱に入れる。

漸化式

を使って計算すると、次表のようになる。

P(n,m)

0

1

2

3

4

5

6

7

8

ΣP(n,m)

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項係数よりやや狭く、分割数はベタっと広がっている。といっても、この特徴から何か意味が読み取れるのか、わからない。


[] [] []