Posts Tagged ‘조합수학’

일대일대응 그리고 카탈란의 수(Catalan Numbers)

Saturday, May 10th, 2008

수를 세다

화면에 나타나 있는 원의 개수를 세어보자.

이 때 우리는 이 원들에 번호를 매겨가면서 수를 셀 수 있다.

무엇이 잘못되었는가? 똑같은 숫자가 두 개의 원에 붙여졌다. 이 때문에 마지막 숫자가 원의 개수와 같지가 않다.

그럼 다음을 보자.

원의 개수는 13개 인가? 아니다. 건너 뛴 숫자가 있기 때문이다.

그럼 다음을 보자.

위에서 얻은 교훈에 의하여 이것이 맞게 세어 졌는가를 확인하기 위해서 우리가 해야 할 일은, 두 가지다.

첫번째로는 같은 숫자가 두 번 이상 등장하지 않는가를 보는 것이고,
두번째는 1부터 12까지의 수가 모두 등장했는지를 보는 것이다.

이 두 가지 테스트를 모두 통과하면 우리는 원의 개수와 마지막에 붙은 수는 같다고 믿을 수 있다.
생각해 보면 우리가 수를 세는 행위는 본질적으로 저것과 같다.
물건을 셀 때, 손가락을 가지고 하나, 둘, 셋 붙여 나가지 않는가.
현실에서 개수가 맞게 세어지지 않은 경우는 다음 중의 하나 일 것이다.

0. 아예 번호가 붙지 않은 것이 있다.
1. 똑같은 물건을 두 번이상 센다.
2. 빼먹은 숫자가 있다.

일대일대응

두 집합 사이에 함수가 존재한다고 할 때, 0번의 조건은 벌써 만족된 것이다.
1번 조건이 의미하는 것은 정의역의 원소가 서로 다른 것으로 대응됨을 뜻한다.
2번 조건은 공역의 원소가 빠짐없이 정의역의 원소에 의하여 대응되었음을 의미한다.

이러한 조건이 성립하면 두 집합의 원소의 개수는 같게 된다.
의식하지는 않지만,수를 센다는 것은 세는 것과 자연수 사이의 일대일대응을 만들어 주는 것이다.
매우 간단해 보이지만 일대일대응은 무한의 개수도 셀 수 있게 한다.

문제

문제는 이것이다.
우리는 (0,0)에서 (n,n)까지 가야 한다. 단 y=x를 넘어서서는 안 된다는 것이다.
몇 가지 방법이 있겠는가? 물론 최단거리로 간다.

문제해결

(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구한 다음,
그 중에서 y=x를 넘어서 가는 방법의 수를 빼면 된다. 이 방법의 수가 얼마가 되겠느냐를 구하는 과정에서 일대일대응이 등장한다.

일단계

(0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수를 구해 보자.
이것은 매우 간단한 문제인데, 일대일대응을 통하여 문제를 풀어보자.
각 경로에서 x축으로 움직이는 것을 X로 표시하고 y축으로 움직이는 것을 Y로 표시하면, 각 경로는 X와Y를 n개 씩 쓴 문자열로 표현된다. 이것이 일대일 대응이다. 각각의 경로는 서로 다른 문자열로 표현될테고, 문자열은 또한 어떤 경로를 표현할테니까 말이다.
따라서 죽 늘어놓은 2n개 중에서 n개를 골라 X라고 써 놓으면 나머지 위치는 Y가 될 것이고 결정될 것이고, 그런 방법의 수는 이다.
즉, (0,0)에서 (n,n)까지 갈 수 있는 모든 방법의 수는 이다.

이단계

이제 y=x를 넘어서서 가는 경로의 수를 구하자. 경로는 반드시 y=x+1과 만나게 될 것이다.

이 때, 이 경로의 (0,0)에서부터 y=x+1과 처음으로 만나는 점까지를 잘라서, y=x에 대칭시키자.

그리고 나머지 경로를 평행이동시켜 대칭이동된 경로에 갖다붙이자.

그 결과는 (0,0)에서 출발하여 (n+1,n-1)에 도착하는 경로일 것이다.

위에서 한 작업은 서로 다른 두 경로의 집합 사이에 어떤 대응을 만들어 낸 것이다. 놀랍게도 이러한 대응은 일대일 대응이다.
이러한 대응이 일대일대응임을 보이는 일은 일대일대응을 찾아내는 것보다는 훨씬 쉬운 일이니 이과정은 증명에 엄밀을 기하고 싶은 사람만 해 보도록 하자. 다시 강조하건대 일대일대응임을 보이기 위해서는 두 가지를 생각해야 한다. 첫번째는, 서로 다른 것으로 대응되었는지를 살피고, 두번째는 공역의 모든 원소가 대응되었는지를 살피는 것이다.

y=x를 넘어서서 가는 경로는 (0,0)에서 (n+1,n-1)까지 가는 경로와 일대일 대응되므로 그 개수는 이다.

따라서 처음에 제기했던 문제의 답은 다음과 같다.

이렇게 해서 얻어진 수열 을 catalan number라고 하는데, 이 수는 조합수학에서 꽤나 자주 등장한다.
그 예로 Pick's theorem의 증명과정에서 다각형을 삼각형으로 분할하는 것이 필요했는데, catalan number는 볼록다각형을 삼각형으로 분할 하는데 있어 몇 가지 방법으로 할 수 있는가와 관계가 있다.

카탈란의 수에 대해 더 알고 싶은 사람은 위키 Catalan number 를 참조.

(이 그림들은 내가 예전에 직접 만든 것인데, 참 잘 만들었다 :)