■フリーズの幾何学(その5)

【2】源氏香と非交差分割

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

[1]n=2:{1}∪{2},{1,2}→B2=2

[2]n=3:{1}∪{2}∪{3},{1,2}∪{3},{1,3}∪{2},{2,3}∪{1},{1,2,3}→B3=1+3+1=5

[3]n=4:{1}∪{2}∪{3}∪{4}1通り

{1,2,3}∪{4}など4通り,

{1,2}∪{3,4}など3通り

{1}∪{2}∪{3,4}など6通り

{1,2,3,4}1通り→B4=1+4+3+6+1=15

[4]n=5:B5=52

[5]n=6:B6=203

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

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

  2nCn/(n+1)

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

  8C4/(4+1)=8・7・6・5/24・5=14

B(0)=1

B(1)=1

B(2)=2

B(3)=5

B(4)=15であったが、B(5)=52である。

B(n+1)=C(n,0)B(n)+C(n,1)B(n-1)+C(n,2)B(n-2)+・・・+C(n,n)B(0)

n=4では

B(5)=B(4)+4B(3)+6B(2)+4B(1)+B(0)=52

n=5では

B(6)=B(5)+5B(4)+10B(3)+10B(2)+5B(1)+B(0)=203

 ベル数はエリック・テンプル・ベルにちなんで名付けられたのであるが,ちなみにテンプル・ベルはお寺の鐘の意である.ベル数は,n個の数字をいくつかの空でない部分集合に分ける方法の総数であるから,n個の素因数をもつ数の乗法分割の仕方の数でもある.

  B2=2,B3=5,B4=15,B5=52,B6=203

 たとえば,

  2310=2・3・5・7・11

にはB5=52通りの積の形で表すことができる.

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