Dyck path는 $n \times n$ 격자에서 $(0, 0)$에서 출발해 $y = x$ 직선 위로 넘어가지 않고 $(n, n)$에 도달하는 경로를 의미한다. 이는 올바른 괄호 문자열, 정다각형의 삼각 분할 등과 일대일 대응되며, Dyck path의 경우의 수는 카탈랑 수로 잘 알려져 있다.
이때, Dyck path에서 $2k - 1$번 이동 방향이 바뀌는 경우에 대해서 생각해 보자. 시작은 R로, 끝은 U로 고정되어 있기 때문에 R에서 U로 바뀌는 경우가 $k$번이라 하면, U에서 R로 바뀌는 경우는 $k-1$번이다. R에서 U로 바뀌는 지점을 peak라 하겠다. 우리는 peak가 $k$개인 Dyck path의 개수를 세는 방법을 알아볼 것이다.
어떤 올바른 괄호 문자열 $s = s_1 \cdots s_{2n}$가 있다. 알아보기 쉽게 $($를 $1$로, $)$를 $0$으로 치환하겠다. $s' = 1s_1 \cdots s_{2n}$을 정의하자. $s'$에는 $n + 1$개의 $1$과 $n$개의 $0$이 존재한다. $s$가 올바른 괄호 문자열이므로 $s$의 peak를 $k$개라 하면 다음이 성립한다.
- $s' = 1^{p_1}0^{q_1}1^{p_2}0^{q_2} \cdots 1^{p_k}0^{q_k}$
- $p_i, q_i > 0$
- $p_1 + \cdots + p_k = n + 1$, $q_1 + \cdots + q_k = n$
$p$와 $q$를 결정하는 경우의 수는 $\binom{n}{k-1}\binom{n-1}{k-1}$이다. 각 쌍은 하나의 $s'$을 만들지만 만들어진 $s'$이 항상 올바른 $s'$은 아니다.
괄호 문자열의 회전 변환에 대해서 생각해 보자. 서로 다른 두 괄호 문자열을 회전 변환했을 때 일치하면 두 문자열을 동치라 할 것이다. 예를 들어,
$1^{p_{3}}0^{q_{3}}1^{p_{4}}0^{q_{4}}\cdots 1^{p_{k}}0^{q_{k}}1^{p_{1}}0^{q_{1}}1^{p_{2}}0^{q_{2}}$
올바른 $s'$은 위와 같은 형태이다. 시작점을 제외하고 0에 도달하지 않아야 하며, 끝은 1이어야 한다.
위와 같은 문자열에서 어떤 점이 시작점으로 적합한지 생각해 보자. 마지막 최솟값만이 유일하게 적합함을 쉽게 증명할 수 있다. 최솟값을 $m$, 최솟값의 위치를 $i$라 하자. 마지막 최솟값이므로, $i$이후의 값들은 모두 $0$보다 크다. 회전 변환은 앞의 그래프를 뒤에 이어 붙인 것과 같으므로, 앞의 그래프에 $1 - m$을 더해 생각하자. $i$ 앞에서 나올 수 있는 가장 작은 값도 $m$ 이상이므로 앞에 있는 값들도 모두 $0$보다 크다. 다른 점이 불가능함도 어렵지 않게 증명할 수 있다. 따라서, 모든 문자열이 각각 하나의 올바른 $s'$의 회전 변환들에 일대일 대응된다.
올바른 $s'$의 회전 변환은 $(1^{+}0^{+})^k$로 생각할 수 있다. 올바른 $s'$ 하나 당 $k$개의 회전 변환이 생성된다. 따라서, 올바른 $s'$의 개수는 $\frac{1}{k}\binom{n}{k-1}\binom{n-1}{k-1}
= \frac{1}{n}\binom{n}{k-1}\binom{n}{k}$이다.
올바른 괄호 문자열의 개수는 Dyck path의 개수와 동치이므로, 우리가 구한 값은 $n \times n$ 격자에서 peak가 $k$개인 Dyck 경로의 개수와 같다. 이 수를 Narayana number라고 한다.
$N(n, k) = \frac{1}{n}\binom{n}{k-1}\binom{n}{k}$
$\sum\limits_{k=1}^n N(n, k) = C_n$
Reference:
https://en.wikipedia.org/wiki/Narayana_number
https://math.stackexchange.com/questions/548417/dyck-paths-with-k-peaks
연습 문제:
'기타' 카테고리의 다른 글
| 2차원 세그먼트 트리의 새로운 구현 (0) | 2025.08.05 |
|---|