■集合の分割(その10)

 {1,2,3,・・・,n}を互いに交わらない(空集合でない)部分集合の合併として表し仕方全体をB(n)とし,n次のベル数と呼ばれる.

===================================

【1】第2種スターリング数

n                   計(ベル数)

1:1                 1

2:1 1               2

3:1 3 1             5

4:1 7 6 1           15

5:1 15 25 10 1      52

6:1 31 90 65 15 1   203

B(1)=1,B(2)=2,B(3)=5、B(4)=15,B(5)=52,・・・

===================================

【2】カタラン数

B(4)={{1,2,3,4}},{{1,2,3},{4}},・・・{{1},{2},{3},{4}}などの分割は「源氏香」方式の図式で表すことができる.

 その際,弧が交差しないようにとれる分割を非交差分割という.B(4)=15であるが,{{1,3},{2,4}}のみが交差分割で,その他は非交差分割である.

 非交差分割の個数は,カタラン数

  (2n,n)/(n+1)

で与えられる.n+4のとき,

  (8,4)/5=8・7・6・5/24・5=14

 また,カタラン数の母関数は

  C(z)={1−√(1−4z)}/2z

で与えられる.

===================================