カタラン数

カタラン数の通常型母関数

by nomura · 2024年5月29日

Follow @nomuramath

カタラン数の通常型母関数
カタラン数の通常型母関数は次のようになる。

\sum_{k = 0}^{\infty} C_{k} x^{k} = \frac{1 - \sqrt{1 - 4 x}}{2 x}

-

C_{n}

はカタラン数

\begin{aligned} \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 - 4 x}}{2 x} \\ = \frac{1 - \sqrt{1 - 4 x}}{2 x} (x \to 0 で上側の符号は不適) \end{aligned}

数学言語

在宅ワーカー募集中

スポンサー募集！

ページ情報

タイトル	カタラン数の通常型母関数
URL	https://www.nomuramath.com/eg6kyup2/
SNSボタン	Tweet

カタラン数の組み合わせ論的解釈

カタラン数の定義

C_{n + 1} = \sum_{k = 0}^{n} C_{k} C_{n - k}

カタラン数の漸化式

C_{n + 1} = \frac{2 (2 n + 1)}{n + 2} C_{n}

カタラン数の別表現

C_{n} = \frac{1}{n + 1} C (2 n, n)