カタラン数[2]

カタラン数の漸化式は次式で表されます。$$C_{n+1}=\frac{2(2n+1)}{n+2}C_n=\displaystyle\sum_{k=0}^n C_k C_{n-k}$$












<証明>

\((1)\) 次のカタラン数の式において$$C_n=\frac{{}_{2n}\mathrm{C}_n}{n+1}$$\(n\) を \(n+1\) として計算を進めます。
\begin{alignat}{2}
C_{n+1}&=\frac{{}_{2n+2}\mathrm{C}_{n+1}}{n+2} =\frac{1}{n+2} \cdot \frac{(2n+2)!}{(n+1)!(n+1)!}\\
&=\frac{1}{n+2}\cdot \frac{(2n+2)(2n+1)}{(n+1)^2} \cdot \frac{(2n)!}{n!n!}\\
&=\frac{2(2n+1)}{n+2} \cdot \frac{{}_{2n}\mathrm{C}_n}{n+1}=\frac{2(2n+1)}{n+2} C_n\\
\end{alignat}以上より$$C_{n+1}=\frac{2(2n+1)}{n+2}C_n$$





\(n=4\) のときのカタラン数 \(C_4\) を下図を用いて考えます。

\(A\) から \(B\) までの経路数 \(C_4\) は、次の \((a)(b)\) に分けることが出来ます。

\((a)\) \((1,1)\) を必ず通る場合  \((b)\) \((1,1)\) を通らない場合

\((a)\) の \((1,1)\) を必ず通る場合は \((0,0) \rightarrow (1,1)\) で \(1\,(=C_0)\) 通り。
\((1,1) \rightarrow (4,4)\) で \(C_3\) 通り。よって \(C_0C_3\) 通り。



\((b)\) の経路数は次の \((c)(d)\) に分けることが出来ます。

\((c)\) \((2,2)\) を必ず通る場合  \((d)\) \((2,2)\) を通らない場合

\((c)\) の\((1,1)\) を通らず \((2,2)\) を必ず通る場合は \((1,0) \rightarrow (2,1) \rightarrow (2,2)\) で \(C_1\) 通り。
\((2,2) \rightarrow (4,4)\) で \(C_2\) 通り。よって \(C_1C_2\) 通り。



\((d)\) の経路数は次の \((e)(f)\) に分けることが出来ます。

\((e)\) \((3,3)\) を必ず通る場合  \((f)\) \((3,3)\) を通らない場合

\((e)\) の \((1,1)\) と \((2,2)\) を通らず \((3,3)\) を必ず通る場合は \((1,0) \rightarrow (3,2) \rightarrow (3,3)\) で \(C_2\) 通り。
\((3,3) \rightarrow (4,4)\) で \(C_1\) 通り。よって \(C_2C_1\) 通り。


\((f)\) の \((1,1)\) と \((2,2)\) と \((3,3)\) を通らない場合は \((1,0) \rightarrow (4,3) \rightarrow (4,4)\) で \(C_3\) 通り。(\(C_3C_0\) 通り)


よって \(A\) から \(B\) までの最短経路数は \((a)+(c)+(e)+(f)\) で計算することができるので$$C_4=C_0C_3+C_1C_2+C_2C_1+C_3C_0$$


同様の流れで、カタラン数 \(C_{n+1}\) は次のように表すことが出来ます。$$C_{n+1}=C_0C_n+C_1C_{n-1}+C_2C_{n-2}+ \cdots +C_{n-1}C_1+C_nC_0$$以上より$$C_{n+1}=\displaystyle\sum_{k=0}^n C_k C_{n-k}$$

コメントを残す

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