カタラン数の別表現
カタラン数の別表現
カタラン数は次のようにも表される。
\[ C_{n}=\frac{1}{n+1}C\left(2n,n\right) \]
\[ C_{n}=C\left(2n,n\right)-C\left(2n,n-1\right) \]
カタラン数は次のようにも表される。
(1)
\(n\in\mathbb{N}_{0}\)とする。\[ C_{n}=\frac{1}{n+1}C\left(2n,n\right) \]
(2)
\(n\in\mathbb{N}\)とする。\[ C_{n}=C\left(2n,n\right)-C\left(2n,n-1\right) \]
-
\(C_{n}\)はカタラン数(1)
カタラン数の母関数より、\begin{align*} \sum_{k=0}^{\infty}C_{k}x^{k} & =\frac{1-\sqrt{1-4x}}{2x}\\ & =\frac{1}{2x}-\frac{1}{2x}\sum_{k=0}^{\infty}C\left(\frac{1}{2},k\right)\left(-4x\right)^{k}\\ & =\frac{1}{2x}-\frac{1}{2x}\sum_{k=0}^{\infty}\frac{P\left(\frac{1}{2},k\right)}{k!}\left(-4x\right)^{k}\\ & =\frac{1}{2x}-\frac{1}{2x}\left\{ 1+\sum_{k=1}^{\infty}\frac{P\left(\frac{1}{2},k\right)}{k!}\left(-4x\right)^{k}\right\} \\ & =-\frac{1}{2x}\sum_{k=1}^{\infty}\frac{P\left(\frac{1}{2},k\right)}{k!}\left(-4x\right)^{k}\\ & =-\frac{1}{2x}\sum_{k=1}^{\infty}\frac{\frac{1}{2}}{\frac{1}{2}-k}\cdot\frac{P\left(-\frac{1}{2},k\right)}{k!}\left(-4x\right)^{k}\\ & =\frac{1}{2x}\sum_{k=1}^{\infty}\frac{P\left(-\frac{1}{2},k\right)}{\left(2k-1\right)k!}\left(-4x\right)^{k}\\ & =\frac{1}{2x}\sum_{k=1}^{\infty}\frac{\left(-1\right)^{k}\left(2k-1\right)!}{\left(2k-1\right)k!2^{2k-1}\left(k-1\right)!}\left(-4x\right)^{k}\cmt{P\left(-\frac{1}{2},n\right)=\frac{\left(-1\right)^{n}\left(2n-1\right)!}{2^{2n-1}\left(n-1\right)!}}\\ & =\frac{1}{2x}\sum_{k=1}^{\infty}\frac{2\left(2k-2\right)!}{k!\left(k-1\right)!}x^{k}\\ & =\sum_{k=1}^{\infty}\frac{\left(2k-2\right)!}{k!\left(k-1\right)!}x^{k-1}\\ & =\sum_{k=0}^{\infty}\frac{\left(2k\right)!}{\left(k+1\right)!k!}x^{k}\\ & =\sum_{k=0}^{\infty}\frac{C\left(2k,k\right)}{k+1}x^{k} \end{align*} となる。
これより、係数を比較して
\[ C_{k}=\frac{1}{k+1}C\left(2k,k\right) \] となるので与式は成り立つ。
(2)
(1)より、\begin{align*} C_{n} & =\frac{1}{n+1}C\left(2n,n\right)\\ & =\left(1-\frac{n}{n+1}\right)C\left(2n,n\right)\\ & =C\left(2n,n\right)-\frac{n}{n+1}C\left(2n,n\right)\\ & =C\left(2n,n\right)-C\left(2n,n-1\right) \end{align*} となるので与式は成り立つ。
ページ情報
タイトル | カタラン数の別表現 |
URL | https://www.nomuramath.com/jj9f0sbr/ |
SNSボタン |
カタラン数の通常型母関数
\[
\sum_{k=0}^{\infty}C_{k}x^{k}=\frac{1-\sqrt{1-4x}}{2x}
\]
カタラン数の漸化式
\[
C_{n+1}=\frac{2\left(2n+1\right)}{n+2}C_{n}
\]
カタラン数の定義
\[
C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k}
\]
カタラン数の組み合わせ論的解釈