카탈란 수에 대한 심화발표 예시입니다. 카탈란 수란 프랑스-벨기에 수학자 외젠 샤를 카탈로니아(Eugène Charles Catalan) 의 이름을 따서 붙여진 명칭입니다. 카탈란 수가 등장하는 문제의 예를 들자면 여러 가지가 있습니다.
n쌍의 괄호 (, )를 열고 닫는 방법의 수? 예를 들어 2쌍의 괄호 여닫기에서 (,(,),) 은 가능하지만, (,),),( 은 가능하지 않다. 친구와 2n번의 경기를 하는데 n번 이기고 n번 졌다. 하지만 어느 순간에도 더 많이 진 적은 없었다. 가능한 방법의 수는? n + 2개의 변을 가진 볼록 다각형을 서로 교차하지 않는 선분으로 n개의 삼각형으로 나누는 방법의 수? 하지만 대표적인 것은 다음과 같은 최단경로의 수 문제입니다. (0,0)에서 (n,n)까지 격자점을 따라 움직이는데 대각선을 지나가지 않고 아래로만 지나가는 최단 경로의 수는?
카탈로니아 수는 C_n으로 표시하며, 그 경우의 수는
C_n=1/n+1 _2nC_n으로 알려져 있습니다.
이것에 대해서 두 가지 방법으로 증명해 보겠습니다.
첫 번째 방법은 여집합을 이용하는 것입니다.
전체 경우의 수는 다음과 같습니다.
여기에서 대각선을 아래에서 위로 지나쳐 가는 경로의 수를 뺍니다.
대각선을 지나쳐 처음으로 y=x+1과 만나는 점을 찾습니다.
그 이후의 경로를 뒤집습니다. 그러면 결국은 (0,0)에서 (n-1,n+1)까지의 경로가 얻어집니다. 즉 빼야 할 수는 (0,0)에서 (n-1,n+1)까지의 최단 경로의 수입니다.
거꾸로 (0,0)에서 (n-1,n+1)까지의 최단 경로를 뒤집으면 옳지 않은 경로 하나를 얻을 수 있습니다. 따라서 옳지 않은 경로의 수는 정확히 (0,0)에서 (n-1,n+1)까지의 최단 경로의 수와 같겠네요.
이제 정리하면 됩니다.
두 번째의 방법은 전체 경로를 분류하는 것입니다. 대각선 위에서 위로 움직여간 횟수를 기준으로 분류합니다. 간단히 이것을 위위라고 부르겠습니다. 이것은 위위=4인 경우입니다. 이제 여기서 위위를 하나 줄여보겠습니다. 대각선을 처음 위로 지나쳐 간 지점을 찾습니다. 이후 처음으로 대각선과 만나는 수평 경로를 찾습니다. 이 수평 경로를 기준으로 아래 위를 서로 바꿉니다.
그러면 위위가 정확히 하나 줄어듭니다.
여기서 다시 대각선을 처음 위로 지나쳐간 지점을 찾고 이후 처음으로 대각선과 만나는 수평경로를 찾습니다. 서로 바꿉니다. 역시 위위가 하나 줄어듭니다.
차례로 줄여갈 수 있습니다. 결국 위위가 0인 경로를 찾을 수 있습니다.
반대로도 가능합니다. 마지막으로 대각선을 지나 수평으로 지나간 경로를 찾습니다. 그것을 기준으로 아래 위를 서로 뒤바꿉니다.
이와 같은 방식으로 정확히 n+1 개의 집단으로 구분할 수 있습니다.
따라서 정확히 n+1로 나누면 됩니다.
이상으로 두 가지 방식으로 카탈란 수를 구해보았습니다.
카탈란 수에 대한 심화 발표는
첫째, 카탈란 수를 구하는 문제를 새롭게 찾아볼 수도 있고,
둘째 카탈란 수에 대한 다양한 예시를 새롭게 찾아볼 수도 있으며,
셋째 카탈란 수에 대한 새로운 증명 방법, 예를 들어 점화식을 이용한 방법이 있습니다, 을 찾아볼 수도 있습니다. 다양한 방법으로 심화 발표를 준비해 보시기 바랍니다.