[더플러스수학] 카탈란 수 - 생성함수(4)

2021.08.03 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 점화식(3)

[더플러스수학] 카탈란 수 - 점화식(3)

2021.08.03 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 일반항(2)

[더플러스수학] 카탈란 수 - 일반항(2)

 

앞의 글에서 카탈란 수의 점화식과 일반항에 대하여 유도하였다. 

카탈란 수 \(\displaystyle C_n = \frac{1}{n+1} {}_{2n}\mathrm{C}_{n} \)은 다음의 점화식이 성립한다.

\(\displaystyle C_n =C_0 C_{n-1}+C_1 C_{n-2}+ C_2 C_{n-3}+ \cdots +C_{n-1}C_0 \)

카탈란 수 \(\displaystyle C_n \)의 일반항

\(\displaystyle C_n = \frac{1}{n+1} {}_{2n} \mathrm{C}_{n}= {}_{2n}\mathrm{C}_{n}-{}_{2n}\mathrm{C}_{n-1}\)

이편에서는 생성함수를 통하여 카탈란수의 점화식에서 일반항 \(\displaystyle C_n = \frac{1}{n+1} {}_{2n} \mathrm{C}_{n}\)을 유도해 보자.

먼저 생성함수가 무엇인지는 아래의 글을 참조하자.

2020.10.07 - [수학과 공부이야기] - [수학의 기초] 생성함수에 대하여 (1) [더플러스수학]

[수학의 기초] 생성함수에 대하여 (1) [더플러스수학]

또, 카탈란 수의 생성함수를 구해보면 \(\displaystyle f(x)= \frac{1-\sqrt{1-4x}}{2x} \)가 나오는데 이것을 테일러 급수로 표현하여 \(\displaystyle x^n \)의 계수를 구하고 이를 통해 \(\displaystyle C_n \)의 일반항을 구하려고 한다.

이를 위해 먼저 \(\displaystyle \sqrt{1+x}=(1+x)^{\frac{1}{2}}\)의 테일러 급수를 구해야 한다. 이것을 일반화된 이항정리라고 부르는데 그 식을 다음과 같다.

 

* 이항정리 

자연수 \(\displaystyle n\)에 대하여

\(\displaystyle \begin{align} (1+x)^n &= \sum_{r=0}^n {}_n \mathrm{C}_r x^r  \\&= {}_n \mathrm{C}_0 + {}_n \mathrm{C}_1 x + {}_n \mathrm{C}_2 x^2 + \cdots +{}_n \mathrm{C}_r x^r+ \cdots +{}_n \mathrm{C}_n x^n    \end{align} \)

 

* 일반화된 이항정리

실수 \(\displaystyle \alpha\)에 대하여

\(\displaystyle \begin{align} (1+x)^{\alpha} &= \sum_{r=0}^n {}_{\alpha} \mathrm{C}_r x^r  \\&= {}_{\alpha} \mathrm{C}_0 + {}_{\alpha} \mathrm{C}_1 x + {}_{\alpha} \mathrm{C}_2 x^2 + \cdots +{}_{\alpha} \mathrm{C}_r x^r+ \cdots    \end{align} \)

여기서 

\(\displaystyle  {}_{\alpha} \mathrm{C}_r = \left( \matrix{\alpha\\r}\right)=\frac{\alpha (\alpha-1)(\alpha-2)\cdots(\alpha-r+1)}{r!} \)

을 나타낸다. 이것은 테일러급수(매클로린 급수)의 \(\displaystyle x^ r\)의 계수이다. 그런데 이것을 조합의 형태로 적었다. 

이제 \(\displaystyle   {\alpha}=\frac{1}{2}\)일 때, \(\displaystyle  {}_{\alpha} \mathrm{C}_r \)을 간단히 계산해보자.

\(\displaystyle \begin{align}  {}_{\frac{1}{2}} \mathrm{C}_r &=\frac{\frac{1}{2} (\frac{1}{2}-1)(\frac{1}{2}-2)\cdots(\frac{1}{2}-r+1)}{r!}\\&= \frac{1}{r!} \times{\frac{1}{2} \times \left(\frac{-1}{2}\right)\times\left(\frac{-3}{2}\right)\times \cdots \left\{\frac{-(2r-3)}{2}\right\} }\\&=\frac{1}{r!} \times \frac{(-1)^{r-1}}{2^r}\times\left\{1\times3 \times 5 \times \cdots\times(2r-3)\right\} \\&= \frac{(-1)^{r-1}}{r! \times 2^r }\times \frac{(2r-2)!}{2 \times 4 \times\cdots\times (2r-2)} \\&=\frac{(-1)^{r-1} \times (2r-2)!}{r! \times 2^r \times 2^{r-1}\times (r-1)! }~~\cdots\cdots (1)\end{align}\)

 

이제 점화식

\(\displaystyle C_0 =1,~C_n =C_0 C_{n-1}+C_1 C_{n-2}+ C_2 C_{n-3}+ \cdots +C_{n-1}C_0 ~(n \geq 1) ~~\cdots\cdots (2)\)

을 만족하는 생성함수 \(\displaystyle f(x)=\sum_{r=0}^{\infty}C_r x^r =C_0 +C_1 x+C_2 x^2 + \cdots +C_r x^r +\cdots\)라 두고 우리는 이 함수의 \(\displaystyle x^r\)의 계수 \(\displaystyle C_r \)를 구하면 그것이 카탈란 수의 일반항이다.

또 여기서 \(\displaystyle C_0 C_{n-1}+C_1 C_{n-2}+ C_2 C_{n-3}+ \cdots +C_{n-1}C_0 \)이 생성함수 \(\displaystyle f(x) \)의 제곱의 \(\displaystyle x^{n-1}\)의 계수가 됨을 아래와 같이 보이자.

\(\displaystyle \begin{align} \left\{f(x) \right\}^2 &= \left(C_0 +C_1 x+C_2 x^2 + \cdots +C_r x^r +\cdots \right)^2 \\&=a_0 +a_1 x +a_2 x^2 +\cdots+a_r x^r +\cdots \end{align}\)

라 할 때,

\(\displaystyle a_0 = C_0 \times C_0 \), \(\displaystyle a_1 = C_0 \times C_1 +C_1 \times C_0 \),  \(\displaystyle a_2 = C_0 \times C_2 +C_1 \times C_1 + C_2 \times C_0\), \(\displaystyle \cdots \)

\(\displaystyle a_r = C_0 \times C_r +C_1 \times C_{r-1} + C_2 \times C_{r-2}+\cdots+C_r \times C_0\),

\(\displaystyle \cdots \)

이다. 따라서 (2)식의 양변에 \(\displaystyle x^{n-1} \)을 곱하여 \(\displaystyle \sum_{n=1}^{\infty}\)를 취하자.

\(\displaystyle  \sum_{n=1}^{\infty} C_n x^{n-1}=\sum_{n=1}^{\infty} \left \{ C_0 C_{n-1}+C_1 C_{n-2}+ C_2 C_{n-3}+ \cdots +C_{n-1}C_0 \right\} x^{n-1} \)

위의 식의 좌변은

\(\displaystyle  \begin{align}\sum_{n=1}^{\infty} C_n x^{n-1}&=\frac{1}{x}\sum_{n=1}^{\infty} C_n x^{n}= \frac{1}{x} \left\{\sum_{n=0}^{\infty} C_n x^{n}-C_0 \right\}\\&= \frac{1}{x}\left\{ f(x)-C_0 \right\} =\frac{1}{x}\left\{ f(x)-1 \right\}\end{align}\)

이고 우변은 

\(\displaystyle  \sum_{n=1}^{\infty} \left \{ C_0 C_{n-1}+C_1 C_{n-2}+ C_2 C_{n-3}+ \cdots +C_{n-1}C_0 \right\}x^{n-1} =\left\{f(x)\right\}^2 \)

이므로

\(\displaystyle \frac{1}{x}\left\{ f(x)-1 \right\} =\left\{f(x)\right\}^2 \)

\(\displaystyle \therefore~ x \left\{f(x)\right\}^2 -f(x)+1=0 \)

근의 공식에 의해 \(\displaystyle  f(x)  \)를 구하면

\(\displaystyle f(x)=\frac{1\pm \sqrt{1-4x}}{2x} \)

생성함수 \(\displaystyle f(x) \)는 \(\displaystyle f(x)=C_0 +C_1 x+C_2 x^2 + \cdots +C_r x^r +\cdots\)이고 \(\displaystyle \lim_{x \rightarrow 0+}f(x)=C_0 =1 \)이므로

\(\displaystyle  \lim_{x \rightarrow 0+} \frac{1 + \sqrt{1-4x}}{2x}  =\infty \)

\(\displaystyle  \begin{align} \lim_{x \rightarrow 0+} \frac{1 -\sqrt{1-4x}}{2x}  &= \lim_{x \rightarrow 0+} \frac{4x}{2x(1 + \sqrt{1-4x})}\\&=\lim_{x \rightarrow 0+} \frac{2}{ 1 + \sqrt{1-4x}   }=1\end{align}\)

에서 

\(\displaystyle f(x)=\frac{1- \sqrt{1-4x}}{2x} \)

이다.  이제  이 생성함수 \(\displaystyle f(x)\)의 \(\displaystyle x^n \)의 계수가 카탈란 수의 일반항이다.

\(\displaystyle f(x)\)에서 \(\displaystyle \sqrt{1-4x} \)을 (1)에서 구한 

\(\displaystyle  {}_{\frac{1}{2}} \mathrm{C}_r x^r =\frac{(-1)^{r-1} \times (2r-2)!}{r! \times 2^r \times 2^{r-1}\times (r-1)! } x^r \)

에  \(\displaystyle x\) 대신에  \(\displaystyle -4x\)를  \(\displaystyle r\) 대신  \(\displaystyle (n+1)\)을 대입하자. 그러면 \(\displaystyle (n+1)\)차항을 구할 수 있다.  \(\displaystyle (n+1)\)차항의 계수에  \(\displaystyle (-1)\)을 곱하여  \(\displaystyle 2\)로 나누면 그것이 생성함수 \(\displaystyle f(x)\)의 \(\displaystyle n\)차항의 계수 즉 \(\displaystyle C_n\)이다.

\(\displaystyle  \begin{align}{}_{\frac{1}{2}} \mathrm{C}_{n+1} (-4x)^{n+1} & =\frac{(-1)^{n} \times (2n)!}{(n+1)! \times 2^{n+1} \times 2^{n}\times n! } (-4x)^{n+1}\\&=\frac{(-1)^{n} \times (2n)! \times (-1)^{n+1}4^{n+1}}{(n+1)! \times 2^{n+1} \times 2^{n}\times n! } x^{n+1}\\&=- 2\times \frac{(2n)! }{(n+1)! \times n!}x^{n+1} \cdots \cdots (3)\end{align} \)

따라서

\(\displaystyle   f(x)  \)의  \(\displaystyle n\)차 항의 계수는 \(\displaystyle   \sqrt{1-4x}\)의  \(\displaystyle  (n+1)\)차 항의 계수를  \(\displaystyle -2\)로 나눈 것이다. 즉 

\(\displaystyle \begin{align} C_n &= - 2\times \frac{(2n)! }{(n+1)! \times n!} \times \frac{1}{(-2)} \\&=\frac{(2n)!}{(n+1)!\times n!}=\frac{1}{n+1} \frac{(2n)!}{n! \times n!} \\&=\frac{1}{n+1}{}_{2n}\mathrm{C}_{n}  \end{align} \)

따라서 \(\displaystyle n \geq0\)일 때,

\(\displaystyle   C_n =\frac{1}{n+1}{}_{2n}\mathrm{C}_{n} \)

이다.