Catalan 数の計算について - Red cat の数学よもやま話・新装開店

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

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

作者: 結城浩
出版社/メーカー: SBクリエイティブ
発売日: 2016/04/20
メディア: 単行本
この商品を含むブログ (2件) を見る

$\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}}$