2014/04/11

カタラン数の意味と漸化式

分野: 場合の数  レベル: 数学オリンピック

カタラン数:
$c_n=\dfrac{1}{n+1}{}_{2n}\mathrm{C}_{n}={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}$
で定義されるカタラン数は場合の数の問題で頻繁に登場する。


なお,カタラン数を表す $c$ は小文字,二項係数を表す $C$ は大文字です。

$\dfrac{1}{n+1}{}_{2n}\mathrm{C}_{n}={}_{2n}\mathrm{C}_{n}-{}_{2n}\mathrm{C}_{n-1}$ は二項係数の定義と簡単な計算で示すことができます。

カタラン数の意味

カタラン数は,漸化式 $c_0=1, c_{n+1}=\displaystyle\sum_{i=0}^nc_ic_{n-i}$ を満たす数列です。(この漸化式の解き方は難しいので数列の母関数とその応用例で紹介します)「カタラン数は,この特殊な漸化式の解」に過ぎません。それ以上でもそれ以下でもありません。ただし,この漸化式が場合の数の様々な問題で出現するためカタラン数はいろいろなところで顔を出すというわけです。

カタラン数そのものに組み合わせの意味を結びつけてしまうと様々な組み合わせの問題を統一的に観ることが難しくなります。
例えば「 $n+2$ 角形の三角形分割の数がカタラン数だ!」と覚えてしまうとトーナメントの問題とカタラン数の関係が分かりにくくなります。

組み合わせによる意味付けはあくまで性質であって,カタラン数の本質的な意味は組み合わせ問題で頻繁に出現する漸化式の解と理解しておくのがよいと思います。

カタラン数の同様な例としてフィボナッチ数が挙げられます。フィボナッチ数列は「 $a_0=0, a_1=1, a_n=a_{n-1}+a_{n-2}$ の解でありいろいろな問題に登場する」と理解しておきましょう。
→フィボナッチ数列の一般項と数学的帰納法

以下,カタラン数が満たす漸化式が出現する例を3つ紹介します。

トーナメントとカタラン数

$n+1$ 人によるトーナメント戦の総数 $c_n$ はカタラン数である。(チームは区別せずトーナメントの表だけを考える)

カタラン数とトーナメント

証明

場合分けを用いて $c_{n+1}$ を数える。
$n+2$ 人でトーナメントをするとき,決勝に左側から上がってくる集団が $i+1$ 人の場合,右側は $n-i+1$ 人。左側のトーナメントのやり方は $c_i$ 通りで,右側は $c_{n-i}$ 通り。これを $i=0$ から $n$ まで足し合わせるとカタラン数の漸化式を得る。

最短経路とカタラン数

縦横 $n$ マスの格子において左下から右上まで対角線をまたがずに行く(踏むのはOK)最短経路の数 $c_n$ はカタラン数である

カタラン数と最短経路

証明

場合分けを用いて $c_{n+1}$ を数える。
左下の点$(0, 0)$ からスタートして対角線をはじめて$(i, i)$ で踏み,$(n+1, n+1)$ まで到着する場合の数は,$c_{i-1}c_{n+1-i}$ 通り。
これを $i=1$ から $n+1$ まで足し上げるとカタラン数の漸化式を得る。

三角形分割とカタラン数

へこんでいない $n+2$ 角形に対角線を $n-1$ 本引いて三角形に分割する方法を $c_n$ とおくと,$c_n$ はカタラン数となる。

カタラン数と三角形分割

証明

場合分けを用いて $c_{n+1}$ を数える。
$n+3$ 角形の頂点を順番に $A_0, A_1,\cdots, A_{n+2}$ とする。

与えられた三角形分割に対して,$A_{n+1}A_{n+2}A_i$ が分割された三角形の一つであるような $i$ が $0$ から $n$ の間にただひとつ存在する。

それぞれの $i$ について,そのような三角形分割は $c_{i}c_{n-i}$ 通りあり,これを $i=0$ から $n$ まで足し上げると,カタラン数の漸化式を得る。

カタラン数はフィボナッチ数の次に頻出です

Tag: 漸化式の解き方と応用例まとめ

分野: 場合の数  レベル: 数学オリンピック