카탈란 수열의 일반항 구하기: 조합으로 구하기

1. 서론

저번 포스팅에서 살짝 설명했듯이 카탈란 수는 n x n 격자에서 R과 U를 써서, 즉 오른쪽과 위쪽으로 움직이는 방법으로도 찾을 수 있다고 하였습니다.
그렇다면 카탈란 수를 만족하면서 움직이는 방법은 뭘까요?
저번시간 포스팅을 잘 보신 분들이라면 힌트? 아니 답을 바로 아실 수 있을겁니다!

바로 y=x인 선을 넘어가지 않고 움직이는 경우가 바로 카탈란 규칙을 만족하면서 움직이는 방법인데요(Dyck(뒤크) 경로라고도 한답니다)
그렇다면 n x n의 격자에서 카탈란 규칙을 만족하며 움직이는 Dyck 경로의 수만 찾으면 카탈란 수열의 일반항을 바로 구할 수 있겠네요!?
그리고 경우의 수 찾기면 팩토리얼이나 조합(combination)으로 구해지겠군요?

자, 그럼 바로 카탈란수의 일반항을 찾으러 떠납시다!

(참고로 이번 포스팅의 모든 이미지는 제가 직접 만든 것임을 밝힙니다.)

2. 카탈란 수의 일반항을 구하기 위한 여정

그러나 안타깝게도 뒤크 경로의 수를 직접적으로 구할 수 있는 방법이 없다는 사실... 물론 어떤 한 점마다 경우의 수를 따져가며 구하려면 구할수야 있겠지만은 수학적으로 간단하게 구하기가 쉽지가 않죠.
그리고 재밌게도 뒤크경로를 만족하는 경우보다 만족하지 않는 경우를 찾는게 더 쉽답니다?
그래서 이제부터 저희는 전체사건에서 뒤크경로를 만족하지 않는 사건을 빼주겠습니다.(확률적으로 여사건이라고 하죠?)
그려면 결국 뒤크경로를 만족하는 경우의 수가 나올테고 이것이 결국 카탈란 수 일테니까요!(그리고 더 나아가 카탈란 수열의 일반항이 되겠죠?)

2-1. 천릿길도 한걸음 부터: 일단 n x n 격자 이동 총 경로 구하기

이제 뭘 해야 할지 알았으니 바로 작업 들어갑니다.
전체사건은 n x n 격자에서 오른쪽과 위쪽으로 한칸씩 차례대로 이동하여 시점부터 종점까지 움직이는 경우의 수 입니다. 따라서 시점은 좌하단, 종점은 우상단이 되겠네요.
더불어 중복으로 움직이는게 아니라 딱 오른쪽 n번 위쪽 n번만 이동하므로(결국 총 2n번만 움직이게 되는거죠?) 되돌아서 움직이는건 못합니다.
이미지로 나타내보자면 아래와 같겠습니다.

빨간색 점에서 파란색 점까지, 오른쪽 혹은 위쪽으로 한칸씩 이동하며 오른쪽 n번 위쪽 n번 총 2n번 이동하겠군요.
자, 그럼 사실 경우의 수가 다 풀린겁니다.
총 2n번 움직인다고 하였습니다. 결국 2n개를 순서대로 늫어놓는 경우의 수와 마찬가지겠네요. 2n개를 순서대로 늘어놓는 경우의 수는 쉽게 팩토리얼(!)로 구할 수 있죠?
즉, $ 2n! $ 입니다.

그런데 여기서 오른쪽 혹은 위쪽으로 움직이는 것에 순서가 있나요?
가령 오른쪽 명령(R)이 $ R_{(0 \to 1)}, R_{(1 \to 2)}... $ 이렇게 따로 있어서 맨 처음에 오는 오른쪽 명령이 $ R_{(1 \to 2)} $면 시작점에서 갑자기 워프해서 1에서 2로 이동하나요? 아니죠? R은 n개 중에 어떤 R이 와도 무조건 지금 시점부터 오른쪽으로 간다는 의미니까 R끼리는 순서가 의미가 없습니다. 또한 이는 U도 마찬가지겠지요?
그리고 경우의 수에서 '순서가 상관 없어요~'하는 애들은 전체 나열하는 경우의 수에서 그 해당하는 애들끼리 나열하는 경우를 나눠주면 되니까 아까 전체 경우의 수에서 R n개, U n개를 나열하는 경우의 수를 나눠주면 되겠군요! 나열은 팩토리얼!
즉,

$ \frac{2n!}{n!n!} $

으로 나타낼 수 있겠네요!

전체 경우의 수를 아주 쉽게 구했습니다!

(더불어 조합의 정의에 따라 $ _{2n} C_{n} $이라고 표현할 수도 있겠네요. 그리고 개념도 총 2n개의 자리 중 n개의 자리에 R n개를 순서상관없이 채우는 경우라고 볼 수도 있구요.(그러면 자연스럽게 나머지 자리에 U를 다 채우면 경로가 완성이 되겠죠))

자, 그럼 이미지로도 한번 확인해볼까요?
n=2는 너무 간단하니까 n=3으로해서 모든 경로를 그리고, 여기서 카탈란 수 조건에 맞는 경로는 파란색으로, 위반한 경우는 빨간색으로 그려보겠습니다.

이미지로 보니까 한눈에 들어오죠!?

3 x 3에서 총 이동경로는 20가지(6!/(3!3!)), 이중에서 카탈란 조건을 만족하며 움직이는 경우의 수는 다섯가지!

2-2. Dyck 경로가 아닌 경우의 수 구하기

카탈란 조건(차례로 나열하는 어느 순간에도 R>=U)을 만족하는 경로는 다시말해 y = x 직선을 '넘어가지 않는' 경로라고 했습니다.
여기서 딱 봐도 '넘어가지 않는'이란 말이 참 구하기 어려울 것 같지 않나요?

실제로도 이 조건을 위반하는 '위반 타이밍'이 x점마다 있어서 각 경우의 수를 다 고려하지 않으면 안되는 상황이죠.(반대로 생각하려해도 선과 만나는 경우 그리고 만나지 않는 경우를 다 생각해줘야하죠? 복잡합니다..)

그러면 결과는 같은데 조건을 어떻게 바꿔야 우리가 전체 경로의 경우의 수를 구하듯이 쉽게 구할 수 있을까요?

바로 y = x + 1 직선과 만나는 경우를 세면 됩니다!
맞죠? y = x 직선을 '넘어가면, 그 순간 바로 y = x + 1 직선과 만나게 되니까요!
그러면 바로 '위반 타이밍'이 'y = x+1 직선과 만나는 상황' 한가지로 통일되게 됩니다.(이 조건이면 반대로 생각해도 이 선과 만나지 않는 경우로 단 한가지 조건이네요!)

이미지로보면 좀 더 확실하겠죠? 오렌지색 선이 y = x+1, 하늘색 점이 y = x + 1과 만난 점입니다.

그럼 이 경우는 어떻게 셀 수 있을까... 하면 또 기가 막힌 방법이 있습니다.

2-2-1. 반사원리(Reflextion principle)

자, 지금 조건을 변경해서 조건은 명확해졌지만, 아직도 판 자체가 구하기 어려운 판입니다.

어떻게 보자면 지금 y = x+1 선을 기준으로 ㄱ자를 대칭시켜놓은, ┏ 이런 모양으로 경로가 꺾여있는 것과 마찬가지입니다.
그러면 단순히 펴주면 되겠네요? 어떻게요?
여기서 등장하는 것이 반사원리입니다.
어떤 경로를 가던 처음 y = x + 1선과 만나는 순간, 이 점을 기준으로 지금까지 진행해왔던 경로를 y = x + 1에 대해서 선대칭이동하는 조작을 반사원리라고 합니다.

그렇게 되면 (0, 0)이던 시점은 (-1, 1)로 옮겨지게되죠.

'그러면 문제가 바뀌는거 아니냐!'라고 생각해 볼 수도 있지만, 실제로 처음 만나는 점에서 선대칭이동을하더라도 경우의 수의 차이는 없습니다. 1:1 대응(bijection)이니까요!

자 이미지로 처음 만난 시점부터 대칭을 만들어봤습니다. 아까 하늘 색 점이 위반한 점이라 했는데, 첫 하늘색 점을 기준으로 선대칭이동하였습니다. 보면 실제로 경우의 수는 변화가 없는것을 알 수 있습니다.

2-2-2. 조금 더 쉽게 개념적으로 설명해보자면...

자, 여기서부터는 제가 더 생각해 본 부분인데요, 반사원리가 조금 생소하다 싶은 분께 개념적으로 어떤 상황인지 설명하기 쉬울 것 같아 만들어본 설명입니다.

이번엔 먼저 이미지부터 보시죠

자 일단 오렌지색 경로를 만나면 무조건 안된다고 했습니다.
그 말인 즉슨, 위에서 보이듯이 빨간 네모를 이동하는 모든 경로는 '안되는' 경로입니다.

자 그럼 이 빨간 경로로 들어가는 방법은 아래 파란박스를 이동하며 들어가는 경로일거고, 나오는 경로는 오른쪽 초록박스를 이동하며 움직일 것입니다.

즉, 여기서 시점부터 파란박스를 이동해서 빨간박스를 이동한 뒤 초록박스를 이동하여 종점으로 가는 모든 경로는 '안되는' 경로 인 것입니다.

자 그럼 간단하게 이 경로를 움직이는 방법만 구하면 되겠네요.
아까말했다시피 굽어져 있는 상태이므로 이를 펴면 쉽게 구할 수 있겠죠.

그리고 펴는 방법은 위에서 알아봤듯 반사원리로 파란박스를 옆으로 이동해서 직사각형을 만들어도 되고, 반대로 초록박스를 위로 이동시켜서 직사각형을 만들어도 경우의 수는 같을겁니다.

여기서 초록박스를 이동하게되면, 위에서 본 반사원리를 거꾸로 적용하여, 가장 마지막에 닿은 점을 기준으로 대칭이동시켜 종점이 대칭이동이 되는 꼴이겠죠.

어찌됐든 반사원리든 개념적인 설명이든 이 방법을 사용하면 아주 간단하게 '안되는' 경우의 수를 찾을 수 있습니다.

최종적으로 안되는 경우의 수는 $ \frac{2n!}{(n+1)!(n-1)!} $ 이겠네요!

[(-1,-1) 부터 (n, n)(여기서는 (3, 3))까지 움직이는 경로는 가로로 n+1번 세로로 n-1번, 전체 2n번 움직이는 경로일테니까요]

2-3. 뒤크 경로를 만족하며 움직이는 경로의 경우의 수

다 구했습니다.

이제 전체 경우의 수에서 뒤크경로를 만족하지 않는 경우의 수를 빼 주면 뒤크경로를 만족하는 경우의 수가 나오게 됩니다.
즉,

$ C_n = \frac{2n!}{n!n!} - \frac{2n!}{(n+1)!(n-1)!} $

3. 결론

네, 이미 구했다시피 카탈란 수의 일반항은 바로

$ C_n = \frac{2n!}{n!n!} - \frac{2n!}{(n+1)!(n-1)!} $
이 됩니다!

조합으로 써보자면

$ C_n = {_{2n}C_{n}} - \frac{n}{n+1} {_{2n}C_{n}} = \binom{2n}{n} - \frac{n}{n+1} \binom{2n}{n} $
이렇게 되겠네요!

이렇게 카탈란 수의 일반항을 조합적인 방법을 이용하여 구했습니다!

5. 응용

지금까지 배운 것을 응용해서 n=4와 n=5인 경우도 구해볼까요?

n = 4일 때 전체 경로의 수는

$ \frac{8!}{4!4!} = 70 $

카탈란 수는

$ C_4 = \frac{8!}{4!4!} - \frac{8!}{5!3!} = 70 - 56 = 14$

실제 이미지로 만들어보면

정확히 맞죠?

n = 5일 때 전체 경로의 수는

$ \frac{10!}{5!5!} = 252 $

카탈란 수는

$ C_4 = \frac{10!}{5!5!} - \frac{10!}{6!4!} = 252 - 210 = 42 $

얘도 그려보면,

맞는게 딱 보이네요!

n=6 부터는 계산해봐도 전체 경로 924, $ C_5 = 132 $이므로 더이상은 그리힘... 듭니다만은 그려봅시다

여튼, n=3으로 구했지만, 결국 n에 대하여 전부 성립하는 일반항을 구했습니다!

4. 미리니름

자, 다음번에는 카탈란수의 점화식을 한번 유도해보도록 하겠습니다!