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

카탈란 수란 무엇인가?에 대한 글
2021.08.02 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 (1)

[더플러스수학] 카탈란 수 (1)

카탈란 수의 일반항에 대한 설명글
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 (0,~0)$을 출발하여 $\displaystyle y \leq x$를 만족하는 정숫점(격자점)을 지나 $\displaystyle (n,~n)$에 이르는 경로의 개수이다. 이 경로를 다음과 같이 서로소인 집합으로 분류하자.
$\displaystyle C_n$의 경로 중 $\displaystyle (0, ~0)$에서 첫번째로 $\displaystyle (0,0)$에서 만났기 때문에 두번 째로 $\displaystyle (i,~i) ~(i=1,~2,~\cdots ,~n)$에 만나서 $\displaystyle (n,~n)$에 도달한 경로를 $\displaystyle X_i$라 하면 임의의 $\displaystyle i,~j ~(i \neq j,~1 \leq i,~j \leq n )$에 대하여 $\displaystyle X_i \cap X_j = \phi$이고 $\displaystyle n(X_1 )+n(X_2 )+\cdots + n(X_n )= C_n$이다. 
이제 $\displaystyle X_i$의 개수가 $\displaystyle C_{i-1}\times C_{n-i}$임을 보이자.

위의 그림을 통해 예를 들어 $\displaystyle \mathrm{O}(0,0)$에서 $\displaystyle (8,8)$으로 가는 카탈란 수 중에서 $\displaystyle \mathrm{O}(0,0)$에서 $\displaystyle y=x$와 두번째로 만나는 점이 $\displaystyle (4,4)$이면서 $\displaystyle (8,8)$에 도달하는 방법의 개수 $\displaystyle n(X_4)$는 $\displaystyle \textcolor {red}{ n(X_4) = C_3 \times C_4}$임을 보이자.
먼저 $\displaystyle \mathrm{O}(0,0)$에서 $\displaystyle y=x$와 만나지 않으면서 처음으로 $\displaystyle (4,4)$에 도달하는 방법은 위의 그림에서 원점에서 $\displaystyle (1,0)$으로 가고 붉은 색 경로로 이동하여 $\displaystyle (4,3)$에 도착한 후 $\displaystyle (4,4)$에 가는 경로이다. 여기서 붉은 색의 경로를 $\displaystyle (1,0)$에서 $\displaystyle (4,3)$에 도달하는 경로의 개수는 $\displaystyle C_3$이다. 따라서 그 개수는

$\displaystyle 1 \times C_3 \times 1=C_3$

또, $\displaystyle (4,4)$에서 $\displaystyle (8,8)$에 도달하는 경로는 $\displaystyle y=x$와 만나도 되기 때문에 위의 그림의 파란색 경로의 개수는 $\displaystyle C_4$이다. 
따라서 경로 $\displaystyle n(X_4)$는 $\displaystyle C_3 \times C_4$이다.
경로 $\displaystyle n(X_1)$의 경우는 좀 특히한데, $\displaystyle (0,~0)$에서 $\displaystyle (1,1)$에 도달하는데 $\displaystyle y=x$와 두번째로 만나는 점이 $\displaystyle (1,1)$인 경우의 수는 $\displaystyle C_0$이다. 물론 $\displaystyle C_0 =1$와 $\displaystyle C_1 =1$은 서로 같다 하더라도 다음것과 동일한 규칙으로 연결하기 위해서는 $\displaystyle C_0$로 하는 것이 맞다.
또, $\displaystyle n(X_8)$인 경우는 $\displaystyle y=x$와 만나지 않으면서 $\displaystyle (8, 8)$에 도달하는 방법은 위의 그림을 참조하면 $\displaystyle C_7$이다. 또, $\displaystyle (8, 8)$에서 $\displaystyle (8, 8)$에 $\displaystyle y=x$와 만날 수도 있게 도달하는 방법은 $\displaystyle C_0$이다.
따라서

$\displaystyle n(X_1)=C_0 \times C_7$, $\displaystyle n(X_2)=C_1 \times C_6$, $\displaystyle n(X_3)=C_2 \times C_5$,  $\displaystyle \cdots$, $\displaystyle n(X_8)=C_7 \times C_0$

그러므로 

$\displaystyle C_8 =C_0 C_{7}+C_1 C_{6}+ C_2 C_{5}+ \cdots +C_{7}C_0$

이 과정을 $\displaystyle 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$

이다.
2021.08.06 - [수학과 공부이야기] - [더플러스수학] 카탈란 수 - 생성함수(4)

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

 
과고1학년, 2학년 대신대비를 위해 더플러스수학학원의 구술시스템에서 실제로 하고 있는 문제를 보시려거나 과학고 3학년 AP미적분학을 준비하고자 하거나 대학교1학년 미적분학에 대해 공부하려고 하면 더플러스수학 프리미엄콘텐츠 를 이용해 보세요.
https://naver.me/FsR64KUy

과학고전문더플러스수학 : 네이버 프리미엄콘텐츠