カタラン数の組み合わせ論的解釈

カタラン数の組み合わせ論的解釈
カタラン数は以下の組み合わせ論的解釈がある。

(1)括弧を対応付きで並べる組み合わせ

\(n\)組の括弧()を対応付きで並べる組み合わせはカタラン数\(C_{n}\)になる。

(2)積の計算順序

\(n+1\)個の文字\(a_{1},a_{2},\cdots,a_{n+1}\)の積\(a_{1}a_{2}\cdots a_{n+1}\)をどの順番で計算するかの総数はカタラン数\(C_{n}\)となる。

(3)最短経路の個数

縦横\(n\)マスずつの格子で開始点を左下として終了点を右上とする。
このとき、開始点から終了点までの対角線を跨がない(上を通るのは可)最短経路はカタラン数\(C_{n}\)となる。

(4)トーナメント戦の総数

\(n+1\)人で行うトーナメント戦の総数はカタラン数\(C_{n}\)となる。
ただし人は区別せずにトーナメントのみを考える。

(5)凸多角形の3角形分割

各頂点が区別できる凸\(n+2\)角形に対角線を交わらないように\(n-1\)本引き\(n\)個の3角形に分割する方法はカタラン数\(C_{n}\)となる。

(6)2分木

\(n\)個の分岐(\(n+1\)個の葉)を持つときの2分木の総数はカタラン数\(C_{n}\)となる。

(7)平面グラフの交差

円上に\(2n\)個の区別のできる点があり、全ての点が交差をしないようにある1点と線を結ぶ総数はカタラン数\(C_{n}\)となる。

(1)の例

3組の括弧を対応付きで並べる組み合わせは
()()()
()(())
(()())
(())()
((()))
の\(C_{3}=5\)通りとなる。
()())(や)))(((のように括弧の対応ができていないものは数えない。

(2)の例

\(3+1=4\)文字\(a,b,c,d\)の積の計算順序は
\[ \left(\left(\left(ab\right)c\right)d\right) \] \[ \left(\left(ab\right)\left(cd\right)\right) \] \[ \left(\left(a\left(bc\right)\right)d\right) \] \[ \left(a\left(\left(bc\right)d\right)\right) \] \[ \left(a\left(b\left(cd\right)\right)\right) \] の\(C_{3}=5\)通りある。

(3)の例

縦横3マスの場合次の\(C_{3}=5\)通りとなる。

(4)の例

4人で行うトーナメントは次の\(C_{3}=5\)通りとなる。

(5)の例

凸6角形を4個の3角形に分割する方法は次の\(C_{4}=14\)通りある。

(6)の例

3個の分岐をもつ2分木は次の\(C_{3}=5\)通りある。

(7)の例

円上に6個の区別のできる点があるとき、全ての点をある点と繋ぐ方法は次の\(C_{3}=5\)通りある。

(1)

\(n+1\)組の括弧()があるとき、1番目は必ず左括弧(であり、その左括弧に対応する右括弧)の間に\(k\)組の括弧()があるとすると、それ以降は\(n-k\)組の括弧の組み合わせとなる。
このとき、\(k\)は\(0,1,\cdots n\)の値をとるので、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となり
\begin{align*} 1 & =C_{1}\\ & =C_{0}^{2} \end{align*} より、
\[ C_{0}=1 \] とすればカタラン数になる。
従って、題意は成り立つ。

(2)

\(j\in\mathbb{N}_{0}\)として、\(j+1\)文字での積の計算順序を\(C_{j}\)とする。
全部で\(n+1\)文字あるので最後に計算するときには\(k\in\left\{ 0,1,2,\cdots,n-1\right\} \)として\(k+1\)文字と\(n+1-\left(k+1\right)=n-k\)文字の掛け算となるのでこのとき、\(C_{k+1-1}C_{n-k-1}=C_{k}C_{n-k-1}\)通りとなる。
例えば\(\left(\left(\left(ab\right)c\right)d\right)\)は最後に\(abc\cdot d\)となるので3文字\(\times\)1文字、\(\left(\left(ab\right)\left(cd\right)\right)\)は最後に\(ab\cdot cd\)となるので2文字\(\times\)2文字である。
これより、\(k\)について、0から\(n-1\)まで総和をとれば、
\begin{align*} C_{n} & =\sum_{k=0}^{n-1}C_{k}C_{n-k-1} \end{align*} となり、\(n\rightarrow n+1\)とすれば
\begin{align*} C_{n+1} & =\sum_{k=0}^{n}C_{k}C_{n-k} \end{align*} となる。
また、\(C_{1}=1\)かつ\(C_{0}=1\)である。
従って\(C_{n}\)はカタラン数となる。

(3)

縦横\(n\)マスとすると格子の線は縦横\(n+1\)個となり、開始点を\(\left(0,0\right)\)、終了点を\(\left(n,n\right)\)とする。
最初に対角線上を通る位置を\(\left(k,k\right)\)とすると、\(\left(0,0\right)\rightarrow\left(1,0\right)\rightarrow\left(k,k-1\right)\rightarrow\left(k,k\right)\)までを進み、\(\left(k,k\right)\)から\(\left(n,n\right)\)までを進む。
このとき\(C_{k-1+1-1}C_{n-k+1-1}=C_{k-1}C_{n-k}\)通りの最短経路がある。
これを\(k\)について1から\(n\)まで総和をとれば、
\begin{align*} C_{n} & =\sum_{k=1}^{n}C_{k-1}C_{n-k}\\ & =\sum_{k=0}^{n-1}C_{k}C_{n-k-1} \end{align*} となり、\(n\rightarrow n+1\)とすれば、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となる。
また、\(C_{1}=1\)なので\(C_{0}=1\)とする。
従って\(C_{n}\)はカタラン数となり、題意は成り立つ。

(4)

\(n+1\)人でトーナメントを行い、決勝戦の左側に\(k+1\)人、右側に\(n+1-\left(k+1\right)=n-k\)人あるとすると、このとき\(C_{k}C_{n-k-1}\)通りある。
これを\(k\)について0から\(n-1\)まで総和をとれば、
\begin{align*} C_{n} & =\sum_{k=0}^{n-1}C_{k}C_{n-k-1} \end{align*} となり、\(n\rightarrow n+1\)とすれば、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となる。
また、\(C_{1}=1\)なので\(C_{0}=1\)とする。
従って\(C_{n}\)はカタラン数となり、題意は成り立つ。

(5)

凸\(n+3\)角形の頂点を\(A_{0},A_{1},\cdots,A_{n+1},A_{n+2}\)とする。
この頂点より、3点\(A_{k},A_{n+1},A_{n+2}\)を選び、対角線を引いて3角形\(A_{k}A_{n+1}A_{n+2}\)を作る。
そうすると、\(A_{0},A_{1},\cdots,A_{k-1}\)の凸\(k\)角形と\(A_{k+1},A_{k+2},\cdots,A_{n}\)の凸\(n-k\)角形ができるので、このとき、この2つの凸多角形で\(C_{k}C_{n-k}\)通りの分割ができる。
これを\(k\)について0から\(n\)まで総和をとれば、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となり凸3角形では\(1=C_{1}=C_{0}^{2}\)なので\(C_{0}=1\)とする。
従って\(C_{n}\)はカタラン数となり題意は成り立つ。

(6)

\(n+1\)個の分岐を持つとき1番最初の分岐の左側に\(k\)個の分岐、右側に\(n-k\)個の分岐があるとすると、このとき、\(C_{k}C_{n-k}\)通りある。
これを\(k\)について0から\(n\)まで総和をとればいいので、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となる。
また\(1=C_{1}=C_{0}^{2}\)となるので\(C_{0}=1\)とすればいい。
従って\(C_{n}\)はカタラン数となり、題意は成り立つ。

(7)

\(2n+2\)個の点を\(a_{0},a_{1},\cdots,a_{2n+1}\)として\(a_{0}\)とペアになる点を\(a_{2k+1}\)とする。
このとき、\(a_{1},a_{2},\cdots,a_{2k}\)と\(a_{2k+1},a_{2k+2},\cdots,a_{2n+1}\)の2個に分割され、\(a_{1},a_{2},\cdots,a_{2k}\)で\(C_{k}\)通り、\(a_{2k+2},a_{2k+2},\cdots,a_{2n+1}\)で\(C_{n-k}\)通りとなるので合わせて\(C_{k}C_{n-k}\)通りとなる。
これを\(k\)について0から\(n\)まで総和をとればいいので、
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] となる。
また\(1=C_{1}=C_{0}^{2}\)となるので\(C_{0}=1\)とすればいい。
従って\(C_{n}\)はカタラン数となり、題意は成り立つ。
数学言語
在宅ワーカー募集中
スポンサー募集!

ページ情報
タイトル
カタラン数の組み合わせ論的解釈
URL
https://www.nomuramath.com/oeu7un0n/
SNSボタン