[이산수학] 카탈란 수(Catalan numbers)

이산수학이다. Discrete의 이산이 맞다.

미적분학, 해석학 등에서 실수와 같은 연속체를 다루는 것과 반대로

이산, 셀 수 있는 것들에 대해 다룬다.

학부때 배운 내용 중 어려웠던 내용에 대해서만 포스팅하겠다.

 

이번 포스팅 주제는 카탈란 수이다. (Catalan numbers, 카탈랑 수)

 

별거 아니고 그냥 $\frac{1}{n+1} {2n \choose n}$을 $C_n$, 카탈란수라고 한다.

보면 알듯 $n$의 값에 따라 변한다. 

 

<문제 1> 좌표평면에서 어떤 동점은 오른쪽 또는 위로 1씩 간다고 하자. 이런 방법으로 원점 $ \mathrm{O}(0, 0)$에서 점 $ \mathrm{K} (n, n)$으로 가는 경로에 대하여 다음 물음에 답하여라. (1) 경로의 수를 구하여라. (2) 직선 $y=x$의 아랫부분을 지나는 경로의 수는 ${2n \choose n+1}$임을 보여라. (3) 직선 $y=x$의 아랫부분을 지나지 않는 경로의 수를 구하여라.

 

이 <문제 1>의 (3)을 보자.

그리고 아래 <문제 2>, <문제 3>과 비교해보자.

<문제 2> $n$개의 $1$과 $n$개의 $-1$로 이루어진 길이 $2n$인 수열  $a_1$, $a_2$, $\cdots$ , $a_{2n-1}$, $a_{2n}$ 중에서 모든 $k=1$, $2$, $3$, $\cdots$ , $2n$에 대하여 $a_1+a_2+ \; \cdots \; +a_k \geq 0$을 만족하는 것의 개수 <문제 3> $1$부터 $2n$ 까지 자연수를 각각 한 번 사용하여 $2 \; \times \; n$행렬 $\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \end{bmatrix}$ 을 만들 때 모든 행과 열이 증가하도록 만들 수 있는 행렬의 수

 

<문제 1>(3), <문제 2>, <문제 3> 세가지 모두 정답은 $\frac{1}{n+1} {2n \choose n}$, 즉 카탈란 수다.

그 말은 세 문제 사이에 일대일대응이 존재한다는 말이다.

<문제 1>부터 풀고, 일대일대응은 그 다음에 생각해보겠다.

 

 

(풀이)

<문제 1>

(1) :

가로 $n$칸, 세로 $n$칸인 도로망에서 $ \mathrm{O}$에서 $ \mathrm{K}$로 가는 최단 경로의 수와 같으므로

답은 $ {2n \choose n}$

 

(2) :

$ \alpha $를 직선 $y=x$의 아랫부분을 지나는 경로라고 하자.

$ \alpha $가 직선 $y=x$ 위의 점 $ \mathrm{A}(i, i) $를 지나 처음으로 $y=x$의 아랫부분을 지나는 때가 있을 것이다.

그러면 $ \alpha $는 무조건 $ \mathrm{B}(i+1, i) $를 지나게 된다. 

(당연하지 오른쪽 아니면 위쪽으로밖에 못가는데 $(i, i)$를 지나고 $y=x$밑으로 오려면 $(i+1, i)$로 와야될거아녀)

 

그럼 이제 새로운 경로 $ \beta $를 정의하자.

$ \beta $는 $ \mathrm{O}$에서 $ \mathrm{B} $ 까지는 경로 $ \alpha $와 같고

그 이후로는 $ \alpha $를 직선 $y=x-1$에 대칭 시킨 길을 따라 움직이는 경로라 하자.

 

그렇게 정의된 $ \beta $라는 경로는 $ \mathrm{L}(n+1, n-1)$에 무조건 도달하게 된다.

또, $ \beta $는 $ \mathrm{O} $에서 $ \mathrm{L} $ 까지의 최단 경로이다. 즉, 낭비하지 않고 간단 뜻이다.

 

$\alpha$가 주어지면 $\beta$가 오직 하나 만들어진다.

 

반대로 $\beta$가 주어지면 $ \alpha $ 또한 오직 하나 만들어진다.

왜그런지 모르겠다면 생각해봐라. $ \beta$가 $y=x-1$과 처음 만나는 점이 $ \mathrm{B}$가 되고,

그 $ \mathrm{B}$의 뒷부분은 다시 $y=x-1$에 대칭시키면  $ \alpha$가 나온다.

 

즉, $ \beta $와 $\alpha$ 사이에는 일대일대응이 존재한다.

 

따라서 (2) 직선 $y=x$의 아랫부분을 지나는 경로 $ \alpha $의 수는 

$ \mathrm{O}$에서 $ \mathrm{L}$까지의 최단경로의 수와 같다.

 

따라서 답은 $ {2n \choose n+1} $이다.

 

 

(3) :

위 (1)과 (2)를 이용하여 

$y=x$의 아랫부분을 지나지 않는 경로의 수는 

(2) - (1) =

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

이다. 

 

우리는 특별히 $\frac{1}{n+1}{ 2n \choose n}$을 $ C_n$이라 하고, 카탈란 수라 부를 것이다.

 

즉, (3) 직선 $y=x$의 아랫부분을 지나지 않는 경로의 수는 카탈란 수이다.

 

 

 

그럼 <문제 2>를 다시 보자.

<문제 2> $n$개의 $1$과 $n$개의 $-1$로 이루어진 길이 $2n$인 수열  $a_1$, $a_2$, $\cdots$ , $a_{2n-1}$, $a_{2n}$ 중에서 모든 $k=1$, $2$, $3$, $\cdots$ , $2n$에 대하여 $a_1+a_2+ \; \cdots \; +a_k \geq 0$을 만족하는 것의 개수

 

<문제 2>의 상황과 앞에서 푼 <문제 1> (3)의 상황에 일대일대응이 존재함을 보이자.

 

$1$을 위로 한칸, $-1$을 오른쪽으로 한칸 이라고 생각하자.

그러면 수열 $a_1$, $a_2$, $\cdots$ , $a_{2n-1}$, $a_{2n}$은 $(0, 0)$에서 $(n, n)$ 까지의 최단경로의 수와 같다.

 

또 모든 $k$에 대하여  $a_1+a_2+ \; \cdots \; +a_k \geq 0$을 만족한다는 말은 

경로 위의 모든 점 $(i, j)$에 대하여 $i-j \geq 0$이라는 말이다.

 

즉, <문제 2>의 상황과 <문제 1> (3)의 상황은 일대일대응이 존재한다.

 

따라서 <문제 2>의 답도 카탈란 수이다.

 

 

<문제 3>은 직접 해보자.

 

 

 

이렇게 카탈란 수가 뭔지 알아보았다.

다음 포스팅에서는 일대일대응을 이용한 경우의 수 세기와 관련해서 조금 더 자세하게 알아보겠다.