? カタラン数

COMPASS

真の理解のためのシンプルな数学のノート

数式を枠からはみ出さずに表示するためには, 画面を横に傾けてください(532 ピクセル以上推奨).

カタラン数

理論

カタラン数

定義≪カタラン数(Catalan number)≫

 $n$ 個の A と $n$ 個の B を $1$ 個ずつ並べていくとき, どの段階においても A の個数が B の個数より多くなるような順列の総数をカタラン数(Catalan number)と呼び, $C_n$ で表す. 便宜上, $C_0 = 1$ と定める.

命題≪カタラン数の公式≫

 すべての正の整数 $n$ に対して, \[ C_n = \frac{{}_{2n}\mathrm C_n}{n+1}\] が成り立つ.

証明

 $xy$ 平面上の原点から点 $(n,n)$ に至る経路において, $x$ 軸方向に $1$ だけ進むことを A, $y$ 軸方向に $1$ だけ進むことを B と考えると, $C_n$ は直線 $y = x$ をまたがないような経路の総数である. 直線 $y = x$ をまたぐような経路は, 初めて直線 $y = x$ をまたぐ点までの部分を直線 $y = x+1$ に関して折り返せば, 点 $(-1,1)$ から点 $(n,n)$ に至る経路に対応づけることができる. そのような経路の総数は ${}_{2n}\mathrm C_{n+1}$ である. 直線 $y = x$ をまたいでもよいとしたときの経路の総数は ${}_{2n}\mathrm C_n$ であるから, \begin{align*} C_n &= {}_{2n}\mathrm C_n-{}_{2n}\mathrm C_{n+1} \\ &= \frac{(2n)!}{n!n!}-\frac{(2n)!}{(n+1)!(n-1)!} \\ &= \frac{(2n)!}{n!n!(n+1)}(n+1-n) \\ &= \frac{{}_{2n}\mathrm C_n}{n+1} \end{align*} が成り立つ.

別証明

 $n,$ $r$ を $0 < r \leqq n$ なる整数とする. $n$ 個の A と $r$ 個の B を $1$ 個ずつ並べていくとき, どの段階においても A の個数が B の個数より多くなるような順列の総数を $f(n,r)$ おけば, \[ f(n,r) = {}_{n+r}\mathrm C_r\dfrac{n-r+1}{n+1}\] が成り立つ(こちらの問題を参照). $r = n$ とすると, 求める等式が得られる.

定理≪カタラン数の漸化式≫

 すべての正の整数 $n$ に対して \[ C_{n+1} = \sum_{k = 0}^nC_k\mathrm C_{n-k}\] が成り立つ.

証明

 $xy$ 平面上の原点から, $x$ 軸方向に $1$ だけ進むか $y$ 軸方向に $1$ だけ進むかを繰り返して, 直線 $y = x$ をまたがずに点 $(n+1,n+1)$ まで進む経路を考える. 原点の次に初めて直線 $y = x$ 上の点 $(l,l)$ に到達するような経路の総数は, そのような経路が $2$ 点 $(1,0),$ $(l,l-1)$ を通ることに注意すると, $C_{l-1}C_{n+1-l}$ 通りである. $1 \leqq l \leqq n+1$ なる各整数 $l$ についてこの和をとると, \[ C_{n+1} = \sum_{l = 1}^{n+1}C_{l-1}\mathrm C_{n+1-l} = \sum_{k = 0}^nC_k\mathrm C_{n-k}\] が得られる.

カタラン数で表される数

 カタラン数の意味づけとしては, 次のような解釈が有名である.

例≪カタラン数で表される数≫

(1)
$xy$ 平面上の原点から, $x$ 軸方向に $1$ だけ進むか $y$ 軸方向に $1$ だけ進むかを繰り返して, 点 $(n,n)$ まで進む. このうち, 直線 $y = x$ をまたがないような経路の総数はカタラン数 $C_n$ である.
(2)
$n$ 人が $500$ 円玉を $1$ 枚ずつ, $n$ 人が $1000$ 円札を $1$ 枚ずつ持って一列に並ぶ. このうち, お釣りを用意せずに, 先頭から $1$ 人ずつ $500$ 円を集金できるような並び方の総数はカタラン数 $C_n$ である.
(3)
$n$ 組のかっこ ( ) を正しく並べる方法の総数はカタラン数 $C_n$ である. ただし, 各組のかっこについて, ) よりも先に ( を並べるものとする.
(1)~(3) については定義から直ちに分かる.
(4)
順序を変えずに $2$ 数ずつ $n+1$ 個の数の積 $a_1\cdots a_na_{n+1}$ を計算する方法の総数は, $((a_1a_2)a_3)$ のように積をとるごとにかっこ () をつける表示において, はじめに積をとる $2$ 数を A, 他の各数を A に置き換え, 左側のかっこ ( を忘れて考えると, $n$ 個の A と $n$ 個の右側のかっこ ) を並べる方法に等しく, カタラン数 $C_n$ である.
(5)
$n+1$ 人のトーナメント表を作る方法の総数は, $n+1$ 個の数の積を計算する方法の総数に等しく, カタラン数 $C_n$ である.
(6)
凸 $n+2$ 角形を対角線を引くことで三角形に分割する方法の総数 $T_n$ はカタラン数 $C_n$ である. 実際, 凸 $n+3$ 角形 $\mathrm P_0\cdots \mathrm P_n\mathrm P_{n+1}\mathrm P_{n+2}$ の分割において, 辺 $\mathrm P_{n+1}\mathrm P_{n+2}$ を含む三角形が $\mathrm P_k\mathrm P_{n+1}\mathrm P_{n+2}$ である場合に限定すると, 凸 $k+2$ 角形 $\mathrm P_0\cdots\mathrm P_k\mathrm P_{n+2}$ を三角形に分割する方法が $T_k$ 通り, 凸 $n-k+2$ 角形 $\mathrm P_k\cdots\mathrm P_n\mathrm P_{n+1}$ を三角形に分割する方法が $T_{n-k}$ 通りあるので, 分割の方法は $T_kT_{n-k}$ 通りある. よって, $T_1 = 1,$ $T_{n+1} = \displaystyle\sum_{k = 0}^nT_kT_{n-k}$ が成り立つから, $T_n = C_n$ である.

問題

カタラン数

問題≪カタラン数の公式≫

 $n,$ $r$ を $0 < r \leqq n$ なる整数とし, $l = n+r$ とおく. 同じ大きさの枠が上段に $n$ 個, 下段に $r$ 個だけ, 左端を揃えて隙間なく並べられている. $1$ から $l$ までの $l$ 個の整数を各段の枠の中に $1$ つずつ, 次の条件を満たすように並べる.
  • 各段においては, 枠の中の数は右にいくにしたがって大きくなる.
  • 左から $r$ 個の各列においては, 下段の数は上段の数より大きい.
このような並べ方の総数を $f(n,r)$ とおく. 次のことを示せ.
(1)
$n > r \geqq 2$ のとき, $f(n,r) = f(n-1,r)+f(n,r-1)$ が成り立つ.
(2)
$n \geqq 2$ のとき, $f(n,n) = f(n,n-1)$ が成り立つ.
(3)
$f(n,r) = {}_{n+r}\mathrm C_r\dfrac{n-r+1}{n+1}$ が成り立つ.
[2001 京都府医大]

解答例

(1)
$n > r \geqq 2$ とする. 並べ方の規則により, 整数 $l = n+r$ は上段の $n$ 番目か下段の $r$ 番目にくる.
(i)
$l$ が上段の $n$ 番目にくるとき. $n > r$ に注意すると, 並べ方の総数は上段が $n-1$ 段, 下段が $r$ 段の場合と等しく, $f(n-1,r)$ 通り. 
(ii)
$l$ が下段の $r$ 番目にくるとき. 並べ方の総数は上段が $n$ 段, 下段が $r-1$ 段の場合と等しく, $f(n,r-1)$ 通り.
(i), (ii) は排反であるから, $f(n,r)= f(n-1,r)+f(n,r-1)$ が成り立つ.
(2)
$n = r$ のとき, 整数 $l = 2n$ は下段の右端にくるしかないので, 上段が $n$ 段, 下段が $n-1$ 段の場合と並べ方の総数は等しい. よって, $f(n,n) = f(n,n-1)$ が成り立つ.
(3)
$l\ (\geqq 2)$ に関する数学的帰納法で示す.
(I)
$l = 2$ のとき. $n = r = 1$ であるから, \[ f(1,1) = 1 = {}_{1+1}\mathrm C_1\cdot\frac{1-1+1}{1+1}\] が成り立つ.
(II)
$l$ 未満の整数に対して題意が成り立つとする.
(i)
$r = 1$ のとき. 下段には $2$ から $l = n+1$ までのどの整数がきてもよいから, \[ f(n,r) = n = {}_{n+1}\mathrm C_1\cdot\frac{n-1+1}{n+1}\] が成り立つ.
(ii)
$n = r$ のとき. (2) の結果と帰納法の仮定から, \begin{align*} f(n,n) &= f(n,n-1) \\ &= {}_{n+(n-1)}\mathrm C_{n-1}\cdot\frac{n-(n-1)+1}{n+1} \\ &= \frac{(2n-1)!}{n!(n-1)!}\cdot\frac{2}{n+1} \\ &= \frac{(2n)!}{n!n!}\cdot\frac{n}{2n}\cdot\frac{2}{n+1} \\ &= \frac{(2n)!}{n!n!}\cdot\frac{1}{n+1} \\ &= {}_{2n}\mathrm C_n\cdot\frac{n-n+1}{n+1} \end{align*} が成り立つ.
(iii)
$n > r \geqq 2$ のとき. (1) の結果と帰納法の仮定から, \begin{align*} &f(n,r) = f(n-1,r)+f(n,r-1) \\ &= {}_{(n-1)+r}\mathrm C_r\cdot\frac{(n-1)-r+1}{(n-1)+1} \\ &\qquad +{}_{n+(r-1)}\mathrm C_{r-1}\cdot\frac{n-(r-1)+1}{n+1} \\ &= \frac{(n+r-1)!}{(n-1)!r!}\cdot\frac{n-r}{n} \\ &\qquad +\frac{(n+r-1)!}{n!(r-1)!}\cdot\frac{n-r+2}{n+1} \\ &= \frac{(n+r-1)!}{n!(r-1)!}\left(\frac{n-r}{r}+\frac{n-r+2}{n+1}\right) \\ &= \frac{(n\!+\!r\!-\!1)!}{n!(r\!-\!1)!}\!\cdot\!\frac{(n\!-\!r)(n\!+\!1)\!+\!r(n\!-\!r\!+\!1)}{r(n\!+\!1)} \\ &= \frac{(n+r-1)!}{n!(r-1)!}\cdot\frac{n^2-r^2+n+r}{r(n+1)} \\ &= \frac{(n+r-1)!}{n!(r-1)!}\cdot\frac{(n+r)(n-r+1)}{r(n+1)} \\ &= \frac{(n+r)!}{n!r!}\cdot\frac{n-r+1}{n+1} \\ &= {}_{n+r}\mathrm C_r\cdot\frac{n-r+1}{n+1} \end{align*} が成り立つ.
(I), (II) から, $2$ 以上のすべての整数 $l$ に対して題意が成り立つ.