カタラン数の漸化式
カタラン数の漸化式
カタラン数は次の漸化式を満たす。
\[ C_{n+1}=\frac{2\left(2n+1\right)}{n+2}C_{n} \]
カタラン数は次の漸化式を満たす。
\[ C_{n+1}=\frac{2\left(2n+1\right)}{n+2}C_{n} \]
-
\(C_{n}\)はカタラン数\begin{align*}
C_{n+1} & =\frac{1}{n+2}C\left(2n+2,n+1\right)\\
& =\frac{\left(2n+2\right)\left(2n+1\right)}{\left(n+2\right)\left(n+1\right)\left(n+1\right)}C\left(2n,n\right)\\
& =\frac{2\left(2n+1\right)}{\left(n+2\right)}C_{n}\cmt{\because C_{n}=\frac{1}{n+1}C\left(2n,n\right)}
\end{align*}
ページ情報
| タイトル | カタラン数の漸化式 |
| URL | https://www.nomuramath.com/qbx1fzu4/ |
| SNSボタン |
カタラン数の組み合わせ論的解釈
カタラン数の通常型母関数
\[
\sum_{k=0}^{\infty}C_{k}x^{k}=\frac{1-\sqrt{1-4x}}{2x}
\]
カタラン数の定義
\[
C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k}
\]
カタラン数の別表現
\[
C_{n}=\frac{1}{n+1}C\left(2n,n\right)
\]