ホーム >> 場合の数 >> カタラン数のいろいろな例

カタラン数が関連する組合せ問題の例をいくつか紹介します.



⇨予備知識


カタラン数の復習

カタラン数の定義と性質については,別記事→カタラン数の定義と漸化式で紹介しました.カタラン数は非常に様々な場面で登場します.この記事では,カタラン数が登場するような組合せ問題の例をいくつか紹介します.

カタラン数の定義を知っており,その漸化式を認めれば,この記事の内容を理解するには十分です.

カタラン数の定義: $n=0,1,2,...$ に対し,$n$ 番目のカタラン数 $C_n$ を次のように定義する. $$\large C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}$$

カタラン数の漸化式: カタラン数 $C_n$ は次の漸化式を満たす. $$・\large C_0 =1$$ $$・\large C_{n+1}=\sum_{i=0}^{n} C_iC_{n-i}$$

この漸化式を満たす数列がカタラン数と一致することの証明は別記事で説明します.ここでは,そのことを認めて,話を進めます.

凸多角形の三角形分割

凸多角形を三角形に分割する方法の総数を考えます. 凸多角形とは,直感的にはへこんでいない多角形のことです.
凸多角形
実は,凸多角形を三角形分割する方法の総数はカタラン数と等しいです.

 凸 $n+2$ 角形に $n-1$ 本の対角線をひいて,三角形に分割する方法は $C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}$ 通り.

たとえば,凸五角形を三角形に分割する方法は下図のように,$5$ 通りあります.
凸五角形の三角形分割
この事実の証明は,凸 $n+2$ 角形を三角形に分割する方法の総数を $C_n$ とおき,これが上で述べた漸化式を満たすことを示せばよいです.

証明: 凸 $n+2$ 角形に $n-1$ 本の対角線をひいて,三角形に分割する方法の総数を $C_n$ とおきます.$C_{n+1}$ を数えます.凸 $n+3$ 角形の頂点を時計周りの順に $A_0,A_1...,A_{n+1},A_{n+2}$ とし,これに $n$ 本の対角線をひいて,三角形分割をひとつ与えます.すると,$A_{i}A_{n+1}A_{n+2}$ が分割された三角形となるような $i (0\le i \le n)$ がただひとつ存在します.
凸五角形の三角形分割
このとき,凸 $n+3$ 角形は,三角形 $A_{i}A_{n+1}A_{n+2}$ と,凸 $i+2$ 角形 と凸 $n-i+2$ 角形に分割されます.それぞれの三角形分割の総数は $C_i,C_{n-i}$ なので, $$C_{n+1}=\sum_{i=0}^{n} C_iC_{n-i}$$ が成り立ちます.また,$C_1=1$ なので,この漸化式より, $$C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}$$ であることがわかります.

トーナメント表の作り方

さて,今度はトーナメント表の作り方を考えてみましょう.
実は,トーナメント表 (勝ち抜き戦) の作り方の総数はカタラン数になります.

$n+1$ チームのトーナメント表の作り方は $C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}$ 通り. 

たとえば,$4$ チームのトーナメント表の作り方は下図のように $5$ 通りあります.
トーナメント表の総数

証明: $n+1$ チームのトーナメント表の作り方の総数を $C_n$ とおきます.$C_{n+1}$ を数えます.$n+2$ チームでトーナメント戦をするとき,決勝に左側からあがってきうるチームが $i (1\le i \le n+1)$ チームあるとすると,右側からあがってきうるチームは $n+2-i$ チームあります.このとき,左側の $i$ チームのトーナメントの作り方の総数は $C_{i-1}$,右側の $n+2-i$ チームのトーナメントの作り方の総数は $C_{n+1-i}$ です.したがって, $$C_{n+1}=\sum_{i=1}^{n+1} C_{i-1}C_{n+1-i}$$ すなわち, $$C_{n+1}=\sum_{i=0}^{n} C_iC_{n-i}$$ また,明らかに $C_1=1$ なので,この漸化式より, $$C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}$$ であることがわかります.

階段状の街路の最短経路

最後に,組合せ問題でよくある最短経路問題にカタラン数が登場することを紹介します.

 下図のような $n-1$ 段の階段状の街路がある.地点 $A$ から地点 $B$ まで街路をたどって最短で行く方法は $C_n=\frac{{}_{2n} \mathrm{C} _n}{n+1}$ 通り.
カタラン数,階段

証明: 求める場合の数を $C_n$ とおきます.$C_{n+1}$ を数えます.$n$ 段の階段状の街路において,対角線上の地点に $A=P_0,P_1,...,P_{n}=B$ と番号をふります.
階段状の街路
地点 $A$ から地点 $B$ まで最短で行くとき, 一番はじめに地点 $P_i$ を通るような $i (1\le i \le n)$ が必ず存在します.このとき,$A$ から $P_i$ までの行き方の総数は $i=1$ のときは $2C_{i-1}$ 通り,$1< i \le n$ のときは $C_{i-1}$ 通りです.また,$P_i$ から $B$ までの行き方の総数は $C_{n-i+1}$ 通りです.したがって, $$C_{n+1}=2C_{0}C_{n}+\sum_{i=2}^{n} C_{i+1}C_{n-i+1}=\sum_{i=1}^{n+1} C_{i+1}C_{n-i+1}$$ すなわち, $$C_{n+1}=\sum_{i=0}^{n} C_iC_{n-i}$$ となります.あとは同様です.

このように,カタラン数は様々な組合せ問題に登場する人気者で,非常に重要な数列です.