카탈란 수의 점화식

다음 글

 

이 글의 마지막 부분에서 카탈란 수는 (0, 0)에서 (n, n)까지 $y=x$ 그래프보다 위에 있는 점을 통과하지 않고, 격자점만을 지나며 이동하는 경우의 수라고 하였다.

 

카탈란 수는 다음 일반항으로 정의되는 수열이다.

$C_n=\frac{1}{n+1}{}_{2n}\mathrm{C}_n$

이 일반항이 어떻게 유도되었는지는 이전 글을 찾아보기 바란다. 이번에는 이 수열의 성질을 응용하는데 초점을 맞출 것이다.

---

카탈란 수는 다음 점화식을 가지고 있다.

$C_{n+1}$$=\displaystyle\sum_{i+j=n}C_i C_j$$=C_0C_n+C_1C_{n-1}$$+\cdots $$+C_{n-1}C_1+C_nC_0$

이는 카탈란 수가 경로의 수 문제와 대응됨을 생각하면 어렵지 않게 설명할 수 있다.

A에서 B까지 파란색 위의 점을 지나지 않고 최단경로로 가는 경우의 수는 $C_5$이다. (참고)

 

이제 $y=x$ 위의 점, 즉 (i, i)인 점들을 각각 $P_i$라고 하자. 즉 점 $P_3$는 (3, 3)이고 A는 $P_0$, B는 $P_5$가 된다.

$P_0\rightarrow P_n \rightarrow P_5$의 경로로 A에서 B까지 가는 경우의 수는

$P_0\rightarrow P_n$ : $C_{n-1}$

$P_n\rightarrow P_5$ : $C_{5-n}$

따라서 $C_{n-1}C_{5-n}$이다.

 

이때 (0, 0)에서 (n, n)까지는 가로세로 n의 정사각형이 그려지지만 그렇다고 $C_n$은 아니다. (n, n)까지 가는 중 빨간 선을 거치게 되면 중복되는 경우가 있기 때문이다. $C_4$는 $C_3$의 모든 경우를 이미 포함하고 있음을 생각해보면 이해하기 쉬울 것이다.

빨간선을 거치지 않으려면 단순히 빨간선을 파란 선처럼 생각해서 "밟으면 안 되는 선"으로 생각하고, 정사각형을 한 칸 작게 잡아 $C_n$ 대신 $C_{n-1}$을 계산하면 된다.

 

한편 (n, n)에서 (5, 5)까지 갈 때는 이를 고려하지 않아야 한다. $y=x$를 여러 번 밟는 경로도 있을 것이기 때문이다. 이미 (0, 0)에서 (n, n)으로 가는 경로를 모두 다르게 잡았기 때문에 여기서 경로가 중복되어도 결국은 다른 경우이다.

 

이제 앞서 밝힌 $C_{n-1}C_{5-n}$을 $P_1$부터 $P_4$까지 합의 법칙을 적용하면 다음과 같다.

$C_5=C_0C_4+C_1C_3+C_2C_2C_3C_1+C_4C_0$

 

이것을 일반화하면 다음 점화식이 된다.

$C_{n+1}=\displaystyle\sum_{i+j=n}C_iC_j$

---

카탈란 수는 경로의 수와는 별개로 다음 식과 관련되기 때문에 굉장히 자주 사용된다.

$C_{n+1}=\displaystyle\sum_{i+j=n}C_iC_j=\frac{1}{n+1}{}_{2n}\mathrm{C}_n$

어떤 문제이던 카탈란 수의 점화식꼴로 대응시킬 수 있다면 바로 카탈란수의 일반항 공식을 이용해 답을 낼 수 있는 것이다.

 

카탈란 수로 귀결되는 문제도 정말 많은데 몇 가지를 나열하자면 다음과 같다.

• 경로의 수 문제
• 다각형 나누기 문제
• 이진트리 문제
• 괄호 열고 닫기 문제
• 입출력 문제
• 한 요소가 다른 요소보다 항상 크게 유지하는 문제

문제 유형의 이름은 내가 나름대로 지은 것이니 괜히 뭐라 하진 말자. 각 유형이 어떻게 카탈란 수와 연관되는지는 다음 글에서 다루겠다.