読者です 読者をやめる 読者になる 読者になる

Red cat の数学よもやま話・新装開店

はてなダイアリー「Red cat の数学よもやま話」から徐々にこちらに移行していきます。

Catalan 数の計算について

Catalan 数のことは語らんよ ? …嘘です, ちょっとだけ語らせて !

先だって発売された新刊「数学ガールの秘密ノート/場合の数」に Catalan 数が登場する.

{\displaystyle \mathrm{C}_n = {2n \choose n} - {2n \choose n + 1} = \frac{1}{n + 1} {2n \choose n}.}

同書では, 二項係数を一度階乗を使って書き直して計算していたが, {2n \choose n} は最終的にそのままの形で残るので, 以下のように計算することもできる.

{\begin{align}
  {2n \choose n} - {2n \choose n + 1}
    &= {2n \choose n} - {2n \choose n - 1} \\
    &= {2n \choose n} - \frac{n}{2n + 1} {2n + 1 \choose n} \\
    &= {2n \choose n} - \frac{n}{2n + 1} {2n + 1 \choose n + 1} \\
    &= {2n \choose n} - \frac{n}{2n + 1} \frac{2n + 1}{n + 1} {2n \choose n} \\
    &= {2n \choose n} - \frac{n}{n + 1} {2n \choose n} \\
    &= \frac{1}{n + 1} {2n \choose n}.
\end{align}}