[더플러스수학] 카탈란 수 - 점화식(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)