このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

カタラン数

 {}_{2n}~\mbox{C}_{n}(n=0,1,2,…)の値1,2,6,20,70,252,924,3432,…を順に、1,2,3,4,5,6,7,8,…で割っていくと、1,1,2,5,14,42,132,429,…という数が得られる。

 この数を一般的に書くと次のようになり、これをカタラン数という。

[定義]

\frac{{}_{2n}~\mbox{C}_{n}~}{n+1}=\frac{(2n)!}{n!~(n+1)!}

nのカタラン数はc(n)と表記する。

[補講]{}_{2n}~\mbox{C}_{n}は、パスカルの三角形の偶数段目の中央の値である。 ◇

亜群における因子の順序を変えない括弧の付け方

 亜群Sの2元演算において、演算を意味する記号*を省略して、普通の乗法のようにx*y=xyで与えられているものとする。しかし、亜群は結合律を仮定していないため、例えば2つの積(ab)[{c(de)}f]と[{(ab)c}d](ef)は一致するとは限らない。
 結合律を仮定すると、これらの積は因子の順序を変えなければ、括弧の付け方に関係なく一致し、簡潔にabcdefと略記できる。

[1]亜群Sにおいて、2つの元a,bの積abを考える

 閉鎖律より、その解釈の仕方は一意的である。

[2]亜群Sにおいて、3つの元a,b,cの積abcを考える

 因子の順序が同じでも、次の2通りの括弧の付け方がある。

  • (ab)c
  • a(bc)

[3]亜群Sにおいて、4つの元a,b,c,dの積abcdを考える

 因子の順序が同じでも、次の5通りの括弧の付け方がある。

  • a{(bc)d}
  • a{b(cd)}
  • (ab)(cd)
  • {a(bc)}d
  • {(ab)c}d

[4]亜群Sにおいて、5つの元a,b,c,d,eの積abcdeを考える

 この積をまず、2つの部分に分けるには、次の4通りの場合がある。

  • a(bcde)
  • (ab)(cde)
  • (abc)(de)
  • (abcd)e

 こららの各々がさらに括弧で細分化される。

  • a(bcde)の場合
    • c(0)c(3)通り
  • (ab)(cde)の場合
    • c(1)c(2)通り
  • (abc)(de)の場合
    • c(2)c(1)通り
  • (abcd)eの場合
    • c(3)c(0)通り

 全部で、c(4)=c(0)c(3)+c(1)c(2)+c(2)c(1)+c(3)c(0)=1・5+1・2+2・1+5・1=14通りである。

[n]亜群Sにおいて、n+1個の元の積a0a1…anを考える

 因子の順序が同じでも、c(n)通りの括弧の付け方がある。このc(n)はカタラン数である。

nc(n)備考
011つの元の場合は括弧の付け方が1通りしかない。
11上記の[1]の場合の括弧の付け方の個数と一致する。
22上記の[2]の場合の括弧の付け方の個数と一致する。
35上記の[3]の場合の括弧の付け方の個数と一致する。
414上記の[4]の場合の括弧の付け方の個数と一致する。

 括弧の付け方から、n+1のカタラン数c(n+1)を計算すると、次の漸化式が得られる。

[定理]
c(n+1)
=\Sigma_{r=0}^n~c(r)c(n-r)
=c(0)c(n)+c(1)c(n-1)+~\cdots~+c(n)c(0)

 nが増加するに応じて、c(n)は急激に増加する。
 例えば、c(29)では1015を超える。

 結合律を仮定すると、このカタラン数の個数分の表現がすべて一致するわけである。つまり、2元演算において、結合律は重要な性質であることがわかる。

円周上の点を交差しない弦で結ぶ

[定理]円周上の2n個の点を交差しない弦で結ぶと、その元の個数はカタラン数と一致する。

多角形を三角形に分割する

 1751年初秋に、オイラーは文通仲間であったゴールドバッハに「与えられた多角形を対角線により三角形に分割する仕方は何通りあるのか」という手紙を書いた。

 この問題は、与えられた凸多角形(便宜上n+2角形とする)を互いに交わらないn-1本の対角線によって、n個の三角形に分割する仕方は何通りあるかということである。

[1]三角形の場合、即ちn=1の場合

 対角線が引けず、元々三角形になっているため、分割は1通りである。

[2]四角形の場合、即ちn=2の場合

 対角線は2通り存在し、分割も2通りある。

[3]五角形の場合、即ちn=3の場合

 力づくでも分割数を割り出すことができるが、一貫した原則を立てて、漏れなく重複なく数え上げる方法を考えてみる。

 そこで、与えられた五角形の1つの辺をbを底辺として固定して、他の辺は左から順にa0,a1,a2,a3とする。
 これらの辺をベクトルと考えれば、\vec{a_0}+\vec{a_1}+\vec{a_2}+\vec{a_3}=\vec{b}が成り立つ。

 このとき、2つの辺の合成は1つの対角線になる。

 例えば、次の図は、\{(\vec{a_0}+\vec{a_1})+\vec{a_2}\}+\vec{a_3}=\vec{b}を表す。

 このようなベクトルの合成の仕方を簡単のために、{(a0a1)a2}a3と略記することにすれば、5角形の対角線による3角形への分割の仕方は、a0,a1,a2,a3の括弧の付け方に完全に対応し、結局c(3)=5通りあることがわかる。その5通りとは、次の通りである。

  1. a0{(a1a2)a3}
  2. a0{a1(a2a3)}
  3. (a0a1)(a2a3)
  4. {(a0a1)a2}a3
  5. {a0(a1a2)}a3

 どの分割にも底辺のbを含む3角形(網目のもの)が1つ含まれるから、その左右で分割の仕方を場合分けすることにより、次が成り立つ。

[定理]多角形をn個の三角形に分けると、三角形の個数はカタラン数と一致する。

[補講]オイラーの手紙に記載された問題に挑戦して、カタラン数と一致することを導いたのはセグナーである。
さらに、この問題と括弧の付け方の問題の関連を見抜き、1838年に問題を完全に解決したのがフランスの数学者であるカタランである。 ◇

カタラン数の性質

[定理]c(n)=2^n~\cdot~\frac{1~\cdot~3~\cdot~\cdots~\cdot~(2n-1)}{(n+1)!}

[定理]n=2k-1のときに限り、c(n)は奇数になる。

参考文献

  • 『大学入試問題で語る数論の世界』
  • 『読んで楽しむ代数学』