| [婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる |
カタラン数
Copyright (C) virtual_high_school, 2018
§1. 括弧の付け方の個数
§2. 漸化式を解く
§3. 最短経路の個数
§4. 凸多角形の三角形分割の個数
§∞. 参考文献
瀬山[1]にカタラン数が出てくる。その一般項は
$C_{n} = \frac{1}{n+1} \frac{(2n)!}{n!n!} = \frac{1}{n+1}\times _{2n}C_{n}
$
である。ためしに最初の4項を計算すると
$C_{1}=1,C_{2}=2,C_{3}=5,C_{4}=14$
となる。この本には括弧の付け方の数はカタラン数になると書かれているのだが、なぜそうなるのか、その証明は書かれていない。本稿でその証明を与えよう。
括弧の付け方が何通りあるか、その個数を考える。例えば、3組の括弧で表わすことができるのは
$(((x)))$
$((x))(y)$
$(x)(y)(z)$
$(x)((y))$
$((x)(y)$
の5通りである。つまり、$n=3$組の括弧の付け方は$5$通りである。これがカタラン数 $C_{3}=5$ の例である。
カタラン数の漸化式を導こう。$n+1$組の括弧があったとする。
$((( )( \cdots$
などと括弧が並ぶが、最初の括弧は左括弧である。この左括弧が対応する相方の右括弧がどこかにあるはずだが、それが最初に出てくる右括弧とは限らない。右括弧は$n+1$個あるので、最初の左括弧に対応する右括弧は$k(k=1,2,\cdots,n+1)$番目に出てくる右括弧であると言える。
最初の左括弧と$k$番目の右括弧との間には$k-1$組の括弧があり、その右側には残りの$n+1-k$組の括弧がある。すなわち
$([k-1\mbox{組}])[n+1-k\mbox{組}]$
であるが、左側と右側のそれぞれのグループの括弧の付け方は
$C_{k-1}$通りと、$C_{n+1-k}$通り
だから、積の法則により $n+1$組の括弧の付け方は
$C_{n+1} = \displaystyle \sum_{k=1}^{n+1} C_{k-1} \times C_{n+1-k}$
ここでインデックスの $k$ を $i=k-1$ に変えると
$C_{n+1} = \displaystyle \sum_{i=0}^{n} C_{i} \times C_{n-i}$
$=C_{0} \times C_{n} + C_{1} \times C_{n-1} + \cdots + C_{n-1} \times
C_{1} + C_{n} \times C_{0}$
となる。つまり、カタラン数の第$n+1$項は、添え字の和が $n$ になるすべての積の和である。ここで具体的な意味はないのだが、計算の便宜上$C_{0}=1$としておいたことをお断りしておく。
結局、カタラン数$C_{n+1}$はそれ以前の項 $C_{0},C_{2},\cdots,C_{n}$ を使って算出できる。実際
$C_{0}=1$
$C_{1} =C_{0} \times C_{0}=1$
$C_{2} =C_{0} \times C_{1} + C_{1} \times C_{0}=2$
$C_{3} =C_{0} \times C_{2} + C_{1} \times C_{1} + C_{2} \times C_{1}=2+1+2=5$
のようになる。
漸化式
$C_{n+1} =C_{0} \times C_{n} + C_{1} \times C_{n-1} + \cdots + C_{n-1} \times C_{1} + C_{n} \times C_{0},$
$C_{0}=1$
を満たす数列の一般項、すなわちカタラン数の一般項を求めよう。
ここで数列の母関数を利用する。(以下の証明は松坂[2]を参考にした)
カタラン数列の母関数は
$g(x)=C_{0}+C_{1}x+C_{2}x^{2}+C_{3}x^{3}+\cdots$
である。$n$次の係数がカタラン数$C_{n}$である。これを2乗すると
$(g(x))^{2}=(C_{0}+C_{1}x+C_{1}x^{2}+C_{1}x^{3}+\cdots)(C_{0}+C_{1}x+C_{1}x^{2}+C_{1}x^{3}+\cdots)$
$=C_{0}^{2}+(C_{0}C_{1}+C_{1}C_{0})x+(C_{0}C_{2}+C_{1}C_{1}+C_{2}C_{0})x^{2}$
$+(C_{0}C_{3}+C_{1}C_{2}+C_{2}C_{1}+C_{3}C_{0})x^{3}+\cdots$
$=C_{1}+C_{2}x+C_{3}x^{2}+C_{4}x^{3}+\cdots$
ここでカタランの漸化式を使って係数を書き直した。
したがって
$(g(x))^{2}=\frac{g(x)-C_{0}}{x}$
分母を払って
$x (g(x))^{2}-g(x)+1=0$
これを$g(x)$についての2次方程式と思って解けば
$g(x)=\frac{1 \pm \sqrt{1-4x}}{2x}$
ここで複号のどちらを採用するかを決めなければならない。
$g(0)=C_{0}=1$
だから、ロピタルの定理を使って
$g(0)=\displaystyle \lim_{x \rightarrow 0} \left( \mp \frac{2}{\sqrt{1-4x}}/2 \right)
=\mp 1$
したがって複号は下側を採って
$g(x)=\frac{1 - \sqrt{1-4x}}{2x}$
である。
次に√ (ルート)の部分を級数展開しよう。二項定理によく似た公式で
$(1+x)^{n}=1+ \displaystyle \sum_{k=1}^{\infty} \frac{n!}{k!(n-k)!} x^{k}$
がある（二項級数という）。ここで$n$は自然数とは限らず、実数としてよい。$n=1/2$とすれば
$\sqrt{1+x}=1+ \displaystyle \sum_{k=1}^{\infty} \frac{1}{k!} (\frac{1}{2}) \cdot(-
\frac{1}{2}) \cdot (-\frac{3}{2}) \cdot \cdots \cdot (-\frac{2k-3}{2})
x^{k}$
$=1+ \displaystyle \sum_{k=1}^{\infty} \frac{1}{k!} (\frac{1}{2} \cdot \frac{1}{2}
\cdot \frac{3}{2} \cdot \cdots \cdot \frac{2k-3}{2}) (-1)^{k-1} x^{k}$
$x$を$-4x$に置き換えて
$\sqrt{1-4x}=1- \displaystyle \sum_{k=1}^{\infty} \frac{1}{k!} (\frac{1}{2} \cdot
\frac{1}{2} \cdot\frac{3}{2} \cdot \cdots \cdot \frac{2k-3}{2}) 2^{2k}
x^{k}$
$=1- \displaystyle \sum_{k=1}^{\infty} \frac{1}{k!} ( 1 \cdot 3 \cdot \cdots \cdot
(2k-3)) \cdot 2^{k} x^{k}$
したがって、この級数を$g(x)$に代入すれば
$g(x)=\frac{1}{2x}(1 - \sqrt{1-4x})$
$=\displaystyle \sum_{k=1}^{\infty} \frac{1}{k!} (1 \cdot 3 \cdot \cdots \cdot (2k-3))
\cdot 2^{k-1} x^{k-1}$
ここでインデックスの $k$ を $n=k-1$ に変えて
$g(x)=\displaystyle \sum_{n=0}^{\infty} \frac{1}{(n+1)!} (1 \cdot 3 \cdot \cdots \cdot
(2n-1)) \cdot 2^{n} x^{n}$
この級数の$n$次の係数がカタラン数$C_{n}$だから
$C_{n}= \frac{1}{(n+1)!} (1 \cdot 3 \cdot \cdots \cdot (2n-1)) \cdot
2^{n}$
$=\frac{1}{(n+1)!} \frac{1 \cdot 2 \cdot 3 \cdot \cdots \cdot(2n) }{
2 \cdot 4 \cdot 6 \cdot \cdots \cdot (2n)} \cdot 2^{n}$
$=\frac{1}{(n+1)!} \frac{(2n)!}{ n!}$
$= \frac{1}{n+1} \frac{(2n)!}{n! n!}$
瀬山[1]が挙げている第2の例が対角線を越えない最短経路の方法の個数である。
この本では、1街区東に行く(→)を左括弧に、1街区北に行く(↑)を右括弧に対応させて説明しているが、ここでは漸化式を立ててそれが先のものと同じになることを示すことによって、解いてみよう。
$(n+1)\times (n+1)$個の正方形たちでできた街区があって、南西隅Aを出発し北東隅Bへ向かうのだが、対角線の南東側を通って対角線は越えないのがルールだ。しかし何回か対角線に接するのは許される。やがては北東隅Bに達するから一度も対角線に接しないということはあり得ない。出発後初めて対角線に接する点をPとし、その点が所属する街路が下から数えて(最下端の街路は数えない)$k$本目としよう。出発点AからPまでは$k$街区だけ北上したことになるが、この間一度も対角線に触れていないから、その方法はAの1街区東の点QからPの1街区南の点Rまで行く方法の数、すなわち$C_{k-1}$通りだけある。ただし、ここでも
$C_{0}=1$
としている。よってスタートからゴールまで$n$街区だけ北上する方法は
$C_{n+1}=\displaystyle \sum_{k=1}^{n+1} C_{k-1} \times C{n+1-k}$通り
ある。インデックスを変えれば
$C_{n+1}=\displaystyle \sum_{i=0}^{n} C_{i} \times C{n-i}$
で、この漸化式は括弧の問題とまったく同じなので、この問題の解もカタラン数で与えられる。
遠山[3]で詳しく論じられている問題である。この論文にも母関数の方法が紹介されている。凸多角形を三角形分割する方法が何通りあるかを調べてみよう。具体的に言うと
3角形だと$C_{1}=1$通り、
4角形だと$C_{2}=2$通り、
5角形だと下図に示したように$C_{3}=2+1+2=5$通り
だから、$n+2$角形だと$C_{n}$通りだと予想できる。つまり頂点の個数から2を引いた数を引数とするカタラン数が、求める場合の数であろう。ここで例によって便宜的に$2$角形なら（そんな図形は存在しないのだから、分割数は任意に決めてよい）、分割方法は$C_{0}=1$通りとしよう。
$C_{n+1}$に対応するのは$n+3$角形だから、$n+3$角形から漸化式を導こう。
任意の辺$AB$を固定する。
三角形分割の細胞の中に$\triangle ABP$があるはずだ。この三角形を挟み撃ちにする2つの多角形がある。片方を
$k$角形($k \geq 2$)
とすると、他方は
$n+4-k$角形($n+4-k \geq 2 \Rightarrow k \leq n+2$)
になる。$\triangle ABP$と合わせると頂点の個数は
$3+k+(n+4-k)=n+7$
だが点$A,B$で2度ダブって数え、点$P$では3度数えているから、ダブりの計4を引くとたしかに$n+3$になる。漸化式を作ると
$C_{n+1}= \displaystyle \sum_{k=2}^{n+2} C_{k-2} \times C_{n+2-k}$
インデックスを$k$から$k-2=i$に変えて
$C_{n+1}= \displaystyle \sum_{i=0}^{n} C_{i} \times C_{n-i}$
ただし
$C_{0}=1$
これまた、括弧の問題や最短経路と同じ漸化式だ。だからこれもカタラン数になる。
[1] 瀬山士郎著『読む数学記号』角川ソフィア文庫、2017年11月刊、pp.72-74
[2] 松坂和夫著『現代数学序説-集合と代数』ちくま学芸文庫、2017年12月刊、pp.129-131
[3] 遠山啓著作集 数学教育論シリーズ12『数楽への招待-Ⅱ』太郎次郎社、1981年10月刊、pp.23-32
| [婆茶留高校数学科☆HP] Top pageに戻る このページを閉じる |