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

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

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

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