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

｛１，２，３，・・・，ｎ｝を互いに交わらない（空集合でない）部分集合の合併として表し方全体をＢ（ｎ）とし，ｎ次のベル数と呼ばれる．

［１］ｎ＝２：｛１｝∪｛２｝，｛１，２｝→Ｂ2＝２

［２］ｎ＝３：｛１｝∪｛２｝∪｛３｝，｛１，２｝∪｛３｝，｛１，３｝∪｛２｝，｛２，３｝∪｛１｝，｛１，２，３｝→Ｂ3＝１＋３＋１＝５

［３］ｎ＝４：｛１｝∪｛２｝∪｛３｝∪｛４｝１通り

｛１，２，３｝∪｛４｝など４通り，

｛１，２｝∪｛３，４｝など３通り

｛１｝∪｛２｝∪｛３，４｝など６通り

｛１，２，３，４｝１通り→Ｂ4＝１＋４＋３＋６＋１＝１５

［４］ｎ＝５：Ｂ5＝５２

［５］ｎ＝６：Ｂ6＝２０３

Ｂ（４）＝｛｛１，２，３，４｝｝，｛｛１，２，３｝，｛４｝｝，・・・｛｛１｝，｛２｝，｛３｝，｛４｝｝などの分割は「源氏香」方式の図式で表すことができる．

その際，弧が交差しないようにとれる分割を非交差分割という．Ｂ（４）＝１５であるが，｛｛１，３｝，｛２，４｝｝のみが交差分割で，その他は非交差分割である．非交差分割の個数は，カタラン数

　　2nＣn／（ｎ＋１）

で与えられる．ｎ＝４のとき，

　　8Ｃ4／（４＋１）＝８・７・６・５／２４・５＝１４

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

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

　　Ｂ2＝２，Ｂ3＝５，Ｂ4＝１５，Ｂ5＝５２，Ｂ6＝２０３

　たとえば，

　　２３１０＝２・３・５・７・１１

にはＢ5＝５２通りの積の形で表すことができる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝