카탈란 수 일반항 증명 (AGC072 D)

길이 $2n$의 올바른 괄호문자열의 개수는 $C_n = \frac{1}{n+1} \binom{2n}{n}$임을 보이자.

 

문자열 $s=s_1s_2 \cdots s_{2n}$와 순열 $p = (p_1, p_2, \cdots, p_{2n})$에 대해, 문자열 $s' = s_{p_1}s_{p_2} \cdots s_{p_{2n}}$이 올바른 괄호문자열이면 "$s$가 $p$에 대해 올바르다"고 정의하자.

 

편의상 $n=4$인 경우에 대해서만 설명한다. 일반적인 경우도 동일한 방식으로 증명 가능하다.

 

$$p_1 = (1, 2, 3, 4, 5, 6, 7, 8)$$

$$p_2 = (2, 3, 4, 5, 6, 7, 8, 1)$$

$$p_3 = (4, 5, 6, 7, 8, 3, 1, 2)$$

$$p_4 = (6, 7, 8, 5, 1, 2, 3, 4)$$

$$p_5 = (8, 7, 1, 2, 3, 4, 5, 6)$$

 

라고 하면, $n$개의 여는 괄호와 $n$개의 닫는 괄호로 이루어진 임의의 문자열 $s$는 $p_1, p_2, \cdots, p_{n+1}(=p_5)$ 중 정확히 $1$개의 순열에 대해 올바르다. 또한, 각 순열에 대해 올바른 문자열은 정확히 $C_n$개이다. 따라서, $\binom{2n}{n}$개의 문자열을 크기가 $C_n$인 집합 $n+1$개로 분할할 수 있고, $C_n = \frac{1}{n+1} \binom{2n}{n}$이 성립한다.

 

$s$가 정확히 $1$개의 순열에 대해 올바른 이유는 다음과 같이 보일 수 있다. 다음을 정의하자.

 

$$t_0 = 0$$

$$t_i = \begin{cases} t_{i-1} + 1 & \textrm{if }s_i=\texttt{(} \\ t_{i-1} - 1 & \textrm{else} \end{cases}$$

$$u_l = \min \left( \arg\min t_i \right)$$

$$u_r = \max \left( \arg\min t_i \right)$$

 

$t$는 흔히 "산"이라고 부르는 것이랑 동일하며, $u_l$은 산에서 제일 낮은 지점 중 가장 왼쪽 지점, $u_r$은 산에서 제일 낮은 지점 중 가장 오른쪽 지점을 의미한다.

 

순열 $p_1, p_2, \cdots, p_{n+1}(=p_5)$에 대해 문자열 $s$가 올바를 필요충분조건은 각각 다음과 같다. (증명은 독자에게 맡긴다.)

 

$$u_l = 0$$

$$u_l = 1$$

$$u_l = 3\textrm{ or }u_r = 2$$

$$u_l = 5\textrm{ or }u_r = 4$$

$$u_l = 7\textrm{ or }u_r = 6$$

 

$u_l$과 $u_r$의 기우성이 동일하고 $u_l=0$인 것과 $u_r=2n$인 것은 동치이므로 $s$는 정확히 $1$개의 순열에 대해서만 올바르다. 따라서, 증명이 끝났다.