■カタラン数と漸化式(その3)

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

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

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