논술 카탈란 수

＊카탈란 수

좌표평면에서 오른쪽 또는 위쪽으로 한 칸씩 이동하여 $\displaystyle (0,0)$에서 $\displaystyle (n,n)$까지 가되,직선 $\displaystyle y=x$ 위쪽으로 올라가지 않는 경로의 수를 카탈란 수 $\displaystyle C_n$이라 한다.대각선에 닿는 것은 허용하며, 아무 이동도 하지 않는 경우를 하나로 세어 $\displaystyle C_0=1$로 둔다.

카탈란 수의 일반항은$\displaystyle C_n=\frac{1}{n+1}{}_{2n}\mathrm{C}_n=\frac{(2n)!}{n!(n+1)!}\quad(n\ge 0)$이고, 처음 몇 항은$\displaystyle C_0=1,\ C_1=1,\ C_2=2,\ C_3=5,\ C_4=14,\ C_5=42$이다.

＊대칭을 이용한 계산

$\displaystyle n\ge 1$이라 하자. 조건 없이 $\displaystyle (0,0)$에서 $\displaystyle (n,n)$까지 가는 경로는오른쪽 이동과 위쪽 이동을 각각 $\displaystyle n$번씩 나열하므로 $\displaystyle {}_{2n}\mathrm{C}_n$개이다.여기서 한 번이라도 $\displaystyle y=x$ 위쪽으로 올라가는 경로의 수를 뺀다.

조건을 어긴 경로가 처음으로 직선 $\displaystyle y=x+1$에 닿는 점을 $\displaystyle \mathrm{P}$라 하자.출발점부터 $\displaystyle \mathrm{P}$까지의 부분만 직선 $\displaystyle y=x+1$에 대하여 대칭이동한다.그러면 출발점 $\displaystyle (0,0)$은 $\displaystyle (-1,1)$로 옮겨지고, $\displaystyle \mathrm{P}$와 그 뒤의 경로는 그대로이므로$\displaystyle (-1,1)$에서 $\displaystyle (n,n)$까지 가는 경로가 된다.

거꾸로 $\displaystyle (-1,1)$에서 $\displaystyle (n,n)$까지 가는 경로는 반드시 $\displaystyle y=x+1$에 닿는다.처음 닿는 점까지의 부분을 같은 직선에 대하여 대칭이동하면 원래 경로가 복원된다.따라서 두 경로의 집합은 일대일로 대응한다.

$\displaystyle (-1,1)$에서 $\displaystyle (n,n)$까지는 오른쪽으로 $\displaystyle n+1$번, 위쪽으로 $\displaystyle n-1$번 이동하므로조건을 어긴 경로는 $\displaystyle {}_{2n}\mathrm{C}_{n-1}$개이다. 따라서$\displaystyle \begin{aligned}C_n&={}_{2n}\mathrm{C}_n-{}_{2n}\mathrm{C}_{n-1}\\&=\left(1-\frac{n}{n+1}\right){}_{2n}\mathrm{C}_n\\&=\frac{1}{n+1}{}_{2n}\mathrm{C}_n.\end{aligned}$

＊같은 구조의 문제

여는 괄호와 닫는 괄호를 각각 $\displaystyle n$개씩 써서 올바른 괄호 배열을 만드는 경우의 수도 $\displaystyle C_n$이다.왼쪽부터 어느 곳까지 읽더라도 닫는 괄호가 여는 괄호보다 많아서는 안 된다.여는 괄호를 오른쪽 이동, 닫는 괄호를 위쪽 이동에 대응시키면바로 $\displaystyle y\le x$를 만족하는 경로가 된다.

두 종류의 기호를 각각 $\displaystyle n$개씩 나열하면서,어느 곳까지 세어도 한 종류의 개수가 다른 종류보다 적지 않아야 하는 문제도 같다.총개수가 서로 다르거나 처음부터 개수 차이가 있으면 카탈란 수 공식을 바로 대입할 수는 없지만,경계를 정하고 대칭을 이용해 조건을 어긴 경우를 빼는 아이디어는 그대로 활용할 수 있다.