はじめに

　この記事は日曜数学 Advent Calendar 2024 の 16日目の記事です。

お題を選んだ背景

　毎年、文化の日（11月3日）に開催されている近畿大学数学コンテストに参加しているのですが、2024年度にはカタラン数を応用すると解ける問題が出題されたので、"復習"しようと考えた次第です。

カタラン数とは

　カタラン数*1の一つの定義方法として、 $n+1$ 個の文字の積の括弧の付け方の総数と定義され、 $C_n$ と表されます。要は、積（二項演算）の結合する順番を考える訳です。

　たとえば、 $n=1$ であれば、 $(a_0 a_1)$ の1通りなので $C_1=1$ 。

　 $n=2$ であれば、 $( (a_0 a_1) a_2)$ と、 $(a_0(a_1 a_2) )$ の2通りなので $C_2=2$ となります。ここで、 $a_0 a_1$ を演算したあとに、 $(a_0 a_1)$ と $a_2$ を計算したものが1つ目で、 $a_1 a_2$ を演算したあとに、 $a_0$ と $(a_1 a_2)$ を計算したものが2つ目です。

　 $n=3$ であれば、 $((a_0 a_1)(a_2 a_3) )$ 、 $( ( (a_0 a_1) a_2) a_3)$ 、 $( (a_0(a_1 a_2) )a_3)$ 、 $( (a_0((a_1 a_2)a_3) )$ 、 $(a_0(a_1(a_2 a_3) ) )$ の5通りなので $C_3=5$ となります。

　このカタラン数を二項係数 $\binom{\alpha}{n}$ を用いた数式で表すと、 $C_n = \frac{1}{n+1} \binom{2n}{n}$ となります。

　ここで、（一般化）二項係数は実数 $\alpha$ に対して、 $\binom{\alpha}{n}$ $= \frac{\Gamma (\alpha +1)}{\Gamma (n+1) \Gamma (\alpha -n +1)}$ $= \frac{\alpha (\alpha -1) \cdots (\alpha -n +1 ) }{n !}$ であるとします。また、 $\Gamma(\alpha)$ はガンマ函数と呼ばれる、階乗を拡張させた函数で、自然数 $n$ に対しては $\Gamma(n) = (n-1)!$ となります。

$C_n = \frac{1}{n+1} \binom{2n}{n}$ となることの証明

　こいつの証明には、カタラン数が満たす漸化式と、母函数を用います。

カタラン数は、 $n \ge 1$ で $C_n = \displaystyle \sum_{k=0}^{n-1}$ $C_{k} \cdot C_{n-1-k}$ という漸化式を満たします。ここで、 $C_0 =1$ とします。実際、 $k=0, 1, \cdots , n-1$ のとき、 $(a_0 a_1 \cdots a_k) (a_{k+1} a_{k+2}\cdots a_{n})$ の２つの積（二項演算）を最後に行う場合を考えれば、前半は $C_k$ 通り、後半は $C_{n-1-k}$ 通りとなることから分かります。
さて、次に以下のような母函数(generating function)を用います。母函数とは、問題にしている数列（函数列）を係数にした冪級数のことです。ある数列 $a_n$ と $b_n$ が等しいことを示すのに、母函数が等しいことを用いる証明法は、組合せ論では常套手段だそうです。

　 $F(x) = \displaystyle \sum_{n=0}^{\infty} C_n x^{n} = 1+\displaystyle \sum_{n=1}^{\infty} C_n x^{n}$

　上述の漸化式を代入すると、

　　　 $= 1 + \displaystyle \sum_{n=1}^{\infty} ( \sum_{k=0}^{n-1}$ $C_{k} \cdot C_{n-1-k} ) x^{n}$

　ここで $m=n-1$ と置き換えると、

　　　 $= 1 + \displaystyle \sum_{m=0}^{\infty} ( \sum_{k=0}^{m}$ $C_{k} \cdot C_{m-k} ) x^{m+1}$

　　　 $= 1 + \displaystyle x \sum_{m=0}^{\infty} ( \sum_{k=0}^{m}$ $C_{k} \cdot C_{m-k} ) x^{m}$

　二項係数を考えると、 $\displaystyle \sum_{m=0}^{\infty} ( \sum_{k=0}^{m}$ $C_{k} \cdot C_{m-k} ) x^{m} = (\displaystyle \sum_{m=0}^{\infty} C_m x^{m} )^{2}$ なので、

　 $F(x) = 1 + \displaystyle x ( F(x) )^{2}$ となる。これを $y=xF(x)$ に関する二次方程式だと見ると $y=x+y^{2}$ となり、解の公式より　 $y = \frac{1 \pm \sqrt{1-4x} }{2}$ であるが、さらに $x=0$ のとき $y = 0 \cdot F(0) = 0$ であることを用いると　 $y = \frac{1 - \sqrt{1-4x} }{2}$ である。

　一般二項定理より、 $(1+x)^{\alpha} = \displaystyle \sum_{n=0}^{\infty} \binom{\alpha}{n} x^{n}$ である。

　よって、 $(1-4x)^{\frac{1}{2}} = \displaystyle \sum_{n=0}^{\infty} \binom{\frac{1}{2}}{n} (-4x)^{n} = 1 + \displaystyle \sum_{n=1}^{\infty} \binom{\frac{1}{2}}{n} (-4x)^{n}$

　ここで、 $\binom{\frac{1}{2}}{n} = \frac{ \frac{1}{2} (\frac{1}{2} -1) \cdots (\frac{1}{2} -n +1) }{n!}$ $= \frac{ 1 (-1) \cdots (3 - 2n ) }{ 2^{n} (n!)} = (-1)^{n-1} \frac{ 1 (1) \cdot 3 \cdots (2n -3 ) }{ 2^{n} (n!)}$

　また、 $1 \cdot 3 \cdots (2n -3) = \frac{(2n-2)!}{(n-1)! 2^{n-1}}$ なので、 $\binom{\frac{1}{2}}{n}= (-1)^{n-1} \frac{ (2n-2)!}{ 2^{n} (n!) (n-1)! 2^{n-1}}$

　つまり、 $(1-4x)^{\frac{1}{2}} = 1 + \displaystyle \sum_{n=1}^{\infty} (-1)^{n-1} \frac{ (2n-2)!}{ 2^{n} (n!) (n-1)! 2^{n-1}} (-4x)^{n}$

　であり、整理していくと以下のようになる。

　　　　　 $= 1 + \displaystyle \sum_{n=1}^{\infty} \frac{ 2 \cdot (-1) (2n-2)! }{ n \cdot (n-1)! (n-1)!} x^{n}= 1 - \displaystyle \sum_{n=1}^{\infty} \frac{2}{n} \binom{2n-2}{n-1} x^{n}$

　さきほどの式に当てはめると、 $y = xF(x) = \frac{1 - \sqrt{1-4x} }{2} = \displaystyle \sum_{n=1}^{\infty} \frac{1}{n} \binom{2n-2}{n-1} x^{n}$ なので、 $F(x) = \frac{1 - \sqrt{1-4x} }{2x} = \displaystyle \sum_{n=1}^{\infty} \frac{1}{n} \binom{2n-2}{n-1} x^{n-1} = \displaystyle \sum_{n=0}^{\infty} \frac{1}{n+1} \binom{2n}{n} x^{n}$ で、 $C_n = \frac{1}{n+1} \binom{2n}{n}$ となり証明は完了した。