カタラン数[3]

カタラン数について、次の式が成り立ちます。

\((1)\) カタラン数の母関数$$\frac{1-\sqrt{1-4x}}{2x}=\displaystyle\sum_{n=0}^{\infty} \frac{{}_{2n}\mathrm{C}_n}{n+1}x^n$$
\((2)\) カタラン数の近似式 (ただし \(n\) は十分に大きい数とする。)$$C_n≒\frac{4^n}{n^{\frac{3}{2}}\sqrt{π}}  $$









<証明>

\((1)\) 次のように、カタラン数の母関数を \(g(x)\) と置きます。$$g(x)=\displaystyle\sum_{n=0}^{\infty} C_n x^n=C_0+C_1x+C_2x^2+C_3x^3+C_4x^4+ \cdots $$両辺を \(2\) 乗します。
\begin{alignat}{2}
\{g(x)\}^2&=(C_0+C_1x+C_2x^2+C_3x^3+C_4x^4+ \cdots)(C_0+C_1x+C_2x^2+C_3x^3+C_4x^4+ \cdots)\\
&\\
&=C_0^2+(C_0C_1+C_1C_0)x^2+(C_0C_2+C_1C_1+C_2C_0)x^2+(C_0C_3+C_1C_2+C_2C_1+C_3C_0)x^3+ \cdots \\
\end{alignat}各項の係数で次のカタラン数の漸化式を用います。 $$C_0^2=C_1,  C_0C_1+C_1C_0=C_2,  C_0C_2+C_1C_1+C_2C_0=C_3,  \cdots $$であるから$$\{g(x)\}^2=C_1+C_2x+C_3x^2+C_4x^3+C_5x^4+ \cdots $$両辺に \(x\) を掛けてから \(C_0\) を加えます。
\begin{alignat}{2}
x\{g(x)\}^2+C_0&=C_0+x(C_1+C_2x+C_3x^2+C_4x^3+C_5x^4+ \cdots)\\
&\\
&=C_0+C_1x+C_2x^2+C_3x^3+C_4x^4+ \cdots=g(x)\\
\end{alignat}移行して \(g(x)\) の \(2\) 次方程式と見て、これを解きます。(\(C_0=1\)) $$x\{g(x)\}^2-g(x)+1=0,  g(x)=\frac{1 \pm \sqrt{1-4x}}{2x}$$
ここで始めに置いた \(g(x)\) の式より \(x=0\) のとき \(g(0)=C_0=1\) だが

解 \(g(x)\) の右辺のルートの前の符号を正としたとき$$\displaystyle\lim_{x \to 0} g(x)=\displaystyle\lim_{x \to 0} \frac{1+\sqrt{1-4x}}{2x}=\infty$$ となって \(g(0)=1\) に反するので不適。

ルートの前の符号を負としたとき(ロピタルの定理を用いて)
\begin{alignat}{2}
\displaystyle\lim_{x \to 0} g(x)&=\displaystyle\lim_{x \to 0} \frac{1-\sqrt{1-4x}}{2x}=\displaystyle\lim_{x \to 0} \frac{1}{2}\left\{(-1) \cdot \frac{1}{2}(1-4x)^{-\frac{1}{2}}(-4)\right\}\\
&=\displaystyle\lim_{x \to 0} \frac{1}{2} \cdot 2(1-4x)^{-\frac{1}{2}}=\displaystyle\lim_{x \to 0} \frac{1}{\sqrt{1-4x}}=1\\
\end{alignat}となって、適する。

以上より、カタラン数の母関数は$$g(x)=\frac{1-\sqrt{1-4x}}{2x}$$



上記の母関数を、次の級数展開を用いて変形します。(詳細はこちらです。)$$(1+t)^{α}=\displaystyle\sum_{n=0}^{\infty} \frac{α(α-1)(α-2) \cdots (α-n+1)}{n!}t^n=1+αt+\displaystyle\sum_{n=2}^{\infty} \frac{α(α-1)(α-2) \cdots (α-n+1)}{n!}t^n$$\(\displaystyle α=\frac{1}{2},\,t=-4x\) を代入して式を整理します。
\begin{alignat}{2}
\sqrt{1-4x}&=1-2x+\displaystyle\sum_{n=2}^{\infty} \frac{\frac{1}{2}\left(\frac{1}{2}-1\right)\left(\frac{1}{2}-2\right) \cdots \left(\frac{1}{2}-n+1\right)}{n!}(-4x)^n\\
&=1-2x+\displaystyle\sum_{n=2}^{\infty} \frac{\frac{1}{2}\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right) \cdots \left(-\frac{2n-3}{2}\right)}{n!}(-1)^n \cdot 2^{2n}x^n\\
&=1-2x-\displaystyle\sum_{n=2}^{\infty} \frac{1 \cdot 3 \cdot 5 \cdots (2n-3)}{2^nn!}2^{2n}x^n\\
&=1-2x -\displaystyle\sum_{n=2}^{\infty} \frac{(2n-3)!!}{n!}2^nx^n\\
\end{alignat}両辺を \((-1)\) 倍します。$$-\sqrt{1-4x}=-1+2x+\displaystyle\sum_{n=2}^{\infty} \frac{(2n-3)!!}{n!}2^nx^n$$両辺に \(1\) を加えます。$$1-\sqrt{1-4x}=2x+\displaystyle\sum_{n=2}^{\infty} \frac{(2n-3)!!}{n!}2^nx^n$$両辺を \(2x\) で割ります。シグマのスタートを \(n=1\) とします。$$\frac{1-\sqrt{1-4x}}{2x}=1+\displaystyle\sum_{n=2}^{\infty} \frac{(2n-3)!!}{n!}2^{n-1}x^{n-1}=1+\displaystyle\sum_{n=1}^{\infty} \frac{(2n-1)!!}{(n+1)!}2^nx^n$$階乗を組合せの式へと変形します。
\begin{alignat}{2}
\frac{1-\sqrt{1-4x}}{2x}&=1+\displaystyle\sum_{n=1}^{\infty} \frac{(2n-1)!!}{(n+1)!}2^nx^n=1+\displaystyle\sum_{n=1}^{\infty} \frac{1}{n+1}\cdot \frac{(2n-1)!!}{n!} \cdot \frac{2^n n!}{n!}x^n\\
&=1+\displaystyle\sum_{n=1}^{\infty} \frac{1}{n+1}\cdot \frac{(2n-1)!!(2n)!!}{n!n!}x^n=1+\displaystyle\sum_{n=1}^{\infty} \frac{1}{n+1}\cdot \frac{(2n)!}{n!n!}x^n\\
&=1+\displaystyle\sum_{n=1}^{\infty} \frac{{}_{2n}\mathrm{C}_n}{n+1}x^n=\displaystyle\sum_{n=0}^{\infty} \frac{{}_{2n}\mathrm{C}_n}{n+1}x^n\\
\end{alignat}以上より$$\frac{1-\sqrt{1-4x}}{2x}=\displaystyle\sum_{n=0}^{\infty} \frac{{}_{2n}\mathrm{C}_n}{n+1}x^n$$








\((2)\) 次のようにカタラン数の式を階乗を用いた式へ変形します。
\begin{alignat}{2}
C_n&=\frac{{}_{2n}\mathrm{C}_n}{n+1}=\frac{1}{n+1}\cdot \frac{(2n)!}{n!n!} =\frac{1}{n+1}\cdot \frac{(2n-1)!!(2n)!!}{n!n!}\\
&=\frac{1}{n+1} \cdot \frac{(2n-1)!! \cdot 2^n n!}{n!n!}=\frac{1}{n+1} \cdot \frac{(2n-1)!!2^n}{n!}\\
&=\frac{1}{n+1}\cdot \frac{(2n-1)!!}{2^n n!}4^n=\frac{4^n}{n+1} \cdot \frac{(2n-1)!!}{(2n)!!}  \cdots (A)\\
\end{alignat}ここで次の「ウォリス積」の式より(詳細はこちらです。)$$\displaystyle\prod_{n=1}^{\infty} \frac{4n^2}{4n^2-1}=\frac{π}{2}$$この式を変形します。
\begin{alignat}{2}
\frac{π}{2}&=\displaystyle\prod_{n=1}^{\infty} \frac{4n^2}{4n^2-1}=\displaystyle\prod_{n=1}^{\infty} \frac{(2n)^2}{(2n-1)(2n+1)}\\
&=\displaystyle\lim_{n \to \infty} \frac{2 \cdot 2}{1 \cdot 3} \cdot \frac{4 \cdot 4}{3 \cdot 5} \cdot\frac{6 \cdot 6}{5 \cdot 7} \cdots \frac{(2n-2)(2n-2)}{(2n-3)(2n-1)} \cdot \frac{(2n)(2n)}{(2n-1)(2n+1)}\\
&=\displaystyle\lim_{n \to \infty} \frac{2 \cdot 2}{1 \cdot 1} \cdot \frac{4 \cdot 4}{3 \cdot 3} \cdot\frac{6 \cdot 6}{5 \cdot 5} \cdots \frac{(2n-2)(2n-2)}{(2n-3)(2n-3)} \cdot \frac{(2n)(2n)}{(2n-1)(2n-1)} \cdot \frac{1}{2n+1}\\
&=\displaystyle\lim_{n \to \infty} \frac{2^2}{1^2} \cdot \frac{4^2}{3^2} \cdot \frac{6^2}{5^2} \cdots \frac{(2n-2)^2}{(2n-3)^2} \cdot \frac{(2n)^2}{(2n-1)^2} \cdot \frac{1}{2n+1}\\
&=\displaystyle\lim_{n \to \infty} \left\{\frac{2 \cdot 4 \cdot 6 \cdots (2n-2) \cdot (2n)}{1 \cdot 3 \cdot 5 \cdots (2n-3) \cdot (2n-1)}\right\}^2 \cdot \frac{1}{2n+1}\\
&=\displaystyle\lim_{n \to \infty} \left\{\frac{(2n)!!}{(2n-1)!!}\right\}^2 \cdot \frac{1}{2n+1}\\
\end{alignat}\(n\) は十分に大きい数であるとすると$$\frac{π}{2}≒\left\{\frac{(2n)!!}{(2n-1)!!}\right\}^2 \cdot \frac{1}{2n+1}$$両辺にルートを付けます。$$\sqrt{\frac{π}{2}}≒\frac{(2n)!!}{(2n-1)!!} \cdot \frac{1}{\sqrt{2n+1}}$$すなわち$$\frac{(2n-1)!!}{(2n)!!}≒\frac{1}{\sqrt{2n+1}} \sqrt{\frac{2}{π}}$$この式を \((A)\) に代入します。$$C_n=\frac{4^n}{n+1} \cdot \frac{(2n-1)!!}{(2n)!!}≒\frac{4^n}{n+1} \cdot \frac{1}{\sqrt{2n+1}} \sqrt{\frac{2}{π}}$$\(n+1≒n,\,2n+1≒2n \) とします。以上より$$C_n≒\frac{4^n}{n} \cdot \frac{1}{\sqrt{2n}} \cdot \sqrt{\frac{2}{π}}=\frac{4^n}{n^{\frac{3}{2}}\sqrt{π}}$$










コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です