[더플러스수학] 카탈란 수 - 생성함수(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}$

이다.