カタラン数の通常型母関数
カタラン数の通常型母関数
カタラン数の通常型母関数は次のようになる。
\[ \sum_{k=0}^{\infty}C_{k}x^{k}=\frac{1-\sqrt{1-4x}}{2x} \]
カタラン数の通常型母関数は次のようになる。
\[ \sum_{k=0}^{\infty}C_{k}x^{k}=\frac{1-\sqrt{1-4x}}{2x} \]
-
\(C_{n}\)はカタラン数\begin{align*}
\sum_{k=0}^{\infty}C_{k}x^{k} & =1+\sum_{k=1}^{\infty}C_{k}x^{k}\\
& =1+\sum_{k=0}^{\infty}C_{k+1}x^{k+1}\\
& =1+\sum_{k=0}^{\infty}\sum_{j=0}^{k}C_{j}C_{k-j}x^{k+1}\\
& =1+\sum_{j=0}^{\infty}\sum_{k=j}^{\infty}C_{j}C_{k-j}x^{k+1}\\
& =1+\sum_{j=0}^{\infty}\sum_{k=0}^{\infty}C_{j}C_{k}x^{k+j+1}\\
& =1+x\sum_{j=0}^{\infty}C_{j}x^{j}\sum_{k=0}^{\infty}C_{k}x^{k}\\
& =1+x\LHS^{2}\\
& =\frac{1\pm\sqrt{1-4x}}{2x}\\
& =\frac{1-\sqrt{1-4x}}{2x}\cmt{x\rightarrow0\text{で上側の符号は不適}}
\end{align*}
ページ情報
| タイトル | カタラン数の通常型母関数 |
| URL | https://www.nomuramath.com/eg6kyup2/ |
| SNSボタン |
カタラン数の組み合わせ論的解釈
カタラン数の漸化式
\[
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}
\]
カタラン数の別表現
\[
C_{n}=\frac{1}{n+1}C\left(2n,n\right)
\]