カタラン数[1]

赤球 \(n\) 個と白球 \(n\) 個の合計 \(2n\) 個の色のついた球があり、
これらの球を一つずつ、一つの袋の中に入れていく。
ただし、常に「袋の中の赤球の個数が白球の個数以上になる」ようにする。

このようなルールで球を袋に入れていくときの場合の数を
「カタラン数」と呼び \(C_n\) で表す。


カタラン数について、次の式が成り立ちます。
( \(C\) の左下に添字がある場合は、通常の組み合わせの式とし、
左下に添字が無い場合はカタラン数を表しているものとします。)$$C_n={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}=\frac{{}_{2n}\mathrm{C}_n}{n+1}$$








\((1)\) 例えば \(n=3\) のとき、

すなわち、赤球 \(3\) 個と白球 \(3\) 個の合計 \(6\) 個の球を、
袋の中の「常に赤球の個数が白球の個数以上」となるように
袋に一つずつ入れていくとき、次のような樹形図が書けます。
(\(R=\)赤球, \(W=\)白球)

よって \(n=3\) のとき \(C_3=5\) となります。




上記の樹形図を参考に \(n=4\) のときを考えます。

カタラン数は下図のように
「オレンジの部分を通って \(A\) から \(B\) まで向かうときの最短経路数」と考えることも出来ます。

次に、組み合わせの式を用いてカタラン数を表すことを考えます。

すなわち、カタラン数は
「\(4 \times 4\) の正方形上の格子点を \(A\) から \(B\) まで向かうときの最短経路数 \({}_8\mathrm{C}_4\)」から
「(※)下図の線分 \(CF\) 上の格子点を通って \(A\) から \(B\) へ向かうときの最短経路」を引くことになります。


(※)の数え方を見ていきます。次は全て互いに排反です。

\((α)\) \(A\) から \(C\) へ \([(0,0) \rightarrow (0,1)]\) と進んでから \(B\) へ向かう。

\((β)\) \(A\) から \(D\) へ \([(0,0) \rightarrow (1,0) \rightarrow (1,1) \rightarrow (1,2)]\) と進んでから \(B\) へ向かう。

\((γ)\) \(A\) から \(E\) へ \([(0,0) \rightarrow (1,0) \rightarrow (2,0) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (2,3)]\) と進んでから \(B\) へ向かう。

\((δ)\) \(A\) から \(F\) へ \([(0,0) \rightarrow (1,0) \rightarrow (2,0) \rightarrow (3,0) \rightarrow (3,1) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (3,4)]\) と進んでから \(B\) へ向かう。



ここで線分 \(CF\) を対称軸として、図を折り返して考えると、
上記 \((α)\) から \((δ)\) は次のように考えることに同じです。

\((α)\) \(A \rightarrow C \rightarrow B’\) へと向かう。

\((β)\) \(A \rightarrow D \rightarrow B’\) へと向かう。

\((γ)\) \(A \rightarrow E\rightarrow B’\) へと向かう。

\((δ)\) \(A \rightarrow F \rightarrow B’\) へと向かう。

これらの場合の数の和は \(3 \times 5\) の長方形の格子点上を
\(A\) から \(B’\) へ向かうことに等しく \({}_8 \mathrm{C}_3\) で計算出来ます。

すなわち、組み合わせの式を用いたときは$$C_4={}_8 \mathrm{C}_4-{}_8 \mathrm{C}_3=70-56=14$$

この考えを基に \(C_n\) の式を書くと$$C_n={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}$$となります。組み合わせの式を階乗に直して、計算を進めます。
\begin{alignat}{2}
C_n&={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}=\frac{(2n)!}{n!n!}-\frac{(2n!)}{(n-1)!(n+1)!}\\
&=\frac{(2n)!}{n!n!}-\frac{n}{n+1} \cdot \frac{(2n)!}{n!n!}=\frac{(2n)!}{n!n!} \left(1-\frac{n}{n+1}\right)\\
&=\frac{(2n)!}{n!n!}\cdot \frac{1}{n+1}=\frac{{}_{2n}\mathrm{C}_n}{n+1}\\
\end{alignat}以上より$$C_n={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}=\frac{{}_{2n}\mathrm{C}_n}{n+1}$$



上記の式を用いて、カタラン数のいくつかを計算してみます。
\begin{alignat}{2}
C_0&=\frac{{}_0\mathrm{C}_0}{0+1}=1\\
C_1&=\frac{{}_2\mathrm{C}_1}{1+1}=\frac{2}{2}=1\\
C_2&=\frac{{}_4\mathrm{C}_2}{2+1}=\frac{
6}{3}=2\\
C_3&=\frac{{}_6\mathrm{C}_3}{3+1}=\frac{20}{4}=5\\
C_4&=\frac{{}_8\mathrm{C}_4}{4+1}=\frac{70}{5}=14\\
C_5&=\frac{{}_{10}
\mathrm{C}_5}{5+1}=\frac{9 \cdot 7 \cdot 4}{6}=42\\
C_6&=\frac{{}_{12}\mathrm{C}_6}{6+1}=\frac{11 \cdot 3 \cdot 4 \cdot 7}{7}=132\\
\end{alignat}





コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です