カタラン数の定義
カタラン数の定義
カタラン数は以下の漸化式で定義される。
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] \[ C_{0}=1 \]
カタラン数は以下の漸化式で定義される。
\[ C_{n+1}=\sum_{k=0}^{n}C_{k}C_{n-k} \] \[ C_{0}=1 \]
カタラン数一覧
\[ \begin{array}{|c|c|} \hline n & C_{n}\\ \hline 0 & 1\\ \hline 1 & 1\\ \hline 2 & 2\\ \hline 3 & 5\\ \hline 4 & 14\\ \hline 5 & 42\\ \hline 6 & 132\\ \hline 7 & 429\\ \hline 8 & 1,430\\ \hline 9 & 4,862\\ \hline 10 & 16,796\\ \hline 11 & 58,786\\ \hline 12 & 208,012\\ \hline 13 & 742,900\\ \hline 14 & 2,674,440\\ \hline 15 & 9,694,845\\ \hline 16 & 35,357,670\\ \hline 17 & 129,644,790\\ \hline 18 & 477,638,700\\ \hline 19 & 1,767,263,190\\ \hline 20 & 6,564,120,420\\ \hline 21 & 24,466,267,020\\ \hline 22 & 91,482,563,640\\ \hline 23 & 343,059,613,650\\ \hline 24 & 1,289,904,147,324\\ \hline 25 & 4,861,946,401,452\\ \hline 26 & 18,367,353,072,152\\ \hline 27 & 69,533,550,916,004\\ \hline 28 & 263,747,951,750,360\\ \hline 29 & 1,002,242,216,651,368\\ \hline 30 & 3,814,986,502,092,304 \\\hline \end{array} \]ページ情報
タイトル | カタラン数の定義 |
URL | https://www.nomuramath.com/zmmtg4fi/ |
SNSボタン |
カタラン数の通常型母関数
\[
\sum_{k=0}^{\infty}C_{k}x^{k}=\frac{1-\sqrt{1-4x}}{2x}
\]
カタラン数の組み合わせ論的解釈
カタラン数の別表現
\[
C_{n}=\frac{1}{n+1}C\left(2n,n\right)
\]
カタラン数の漸化式
\[
C_{n+1}=\frac{2\left(2n+1\right)}{n+2}C_{n}
\]