카탈란 수열 문제

반지름을 자유롭게 늘였다 줄일 수 있는 원이 7개가 있다. 원이 서로 만나지 않게 원의 중심을 일직선 위에 배열하려고 한다. 모두 몇 가지 배열이 있을까? 일반적으로 $n$개의 원에 대한 식을 구할 수 있을까?

$n=3$일 때, $5$가지

 

 

$n=4$일 때, $14$가지

수학 문제 풀이는 문제를 간단하게 만들기에서 시작한다.

위 그림 가운데 $n=3$일 때, 그림을 아래와 위를 잘라내면 그림과 같이 달라진다.

이것은 ((())),(()()), (())(), ()(()), ()()()로 생각할 수 있으므로 카탈란 수열 문제(잘 짜여진 괄호)임을 알 수 있다.

또한, ((())),(()())는 $1,1,1,-1,-1,-1$처럼 여는 괄호 '('는 $1$로 닫는 괄호 ')'는 $-1$로 나타내어도 된다.

이제 문제는 동그라미를 그리는 것이 아니라 $1,-1$ 각각 $n$개 씩 나열하는 문제로 생각해 해결할 수 있다.

먼저 이 수열을 $\{C_n \}( n=0,1,2,3,\cdots)$라고 하자.

$n=3$일 때, $1,1,-1,-1,1,-1$은 가능하지만 $1,-1,-1,1,1,-1$은 나올 수 없다. 열었던 괄로를 반드시 닫아야 하므로 1,-1을 계속 더하며 음수가 나오는 순간이 있으면 안 된다. 이제 나올 수 없는 경우를 세기위해 잘못된 $-1$이 나오는 바로 다음에 있는 수의 부호를 바꾸기로 하자.

그러므로 $n=3$일 때는 '$1$'은 3개, '$-1$'은 3개를 한 줄로 늘어놓는 경우의 수에서 '$1$'은 2개 '$-1$'은 4개를 한 줄로 세우는 경우의 수를 빼면 된다.

$$C_3 =\frac{(2\cdot 3)!}{3!3!} -\frac{(2\cdot 3)!}{2!4!}={}_6C_3 -{}_6 C_4 =20-15=5$$

이를 일반화하면

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

더 자세한 이야기는 "카탈란 수"  참고하라.