Catalan Number
카탈란 수는 n+1개의 인수의 곱을 결합법칙이 성립하지 않을 때 표현하는 경우의 수이다.
Cn와 같이 쓴다.
예시로, n=3이면 다음과 같이 5개이다.
- (((ab)c)d)
- ((a(bc))d)
- (a((bc)d))
- (a(b(cd)))
- ((ab)(cd))
두 개씩만 인수들을 묶는다.
이 숫자가 재밌는 이유는, 위와 같이 겉보기엔 단순해보이는 정의가 나타내는 이 수가
굉장히 다양한 문제의 해답으로 표현되기 때문이다.
일반항
C0을 0이라고 한다면,
Cn=1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ⋯
와 같이 증가한다.
Cn=n+11(n2n)=(n+1)!⋅n!(2n)!
이 일반항은 O(N+logp)이 걸리지만, 실제로 수가 커져서 modular inverse를 계산하게끔 나머지를 소수로 주어지는
문제가 아니라면 써먹을 수 없는 방법이다.
Cn=n+12(2n−1)Cn−1(n≥1)
이 일반항은 O(Nlogp) 정도가 걸린다.
Cn=k=0∑n−1CkCn−1−k=C0⋅Cn−1+C1⋅Cn−2+⋯
O(N2) 이지만 이것이 문제에서 가장 흔하다.
Applicable Problems
위에서 들었던 예시대로 문제를 풀어보자.
괄호, 스택 문제
BOJ 10422
이 문제는 O(N2)로 해결할 수 있다.
괄호가 1쌍이라면, () 정답은 1개이다.
2쌍이라면 ()(), (()) 2개이다.
그 이후부터 생각을 해보자.
이번에 추가해야 할 괄호 한 쌍이 () 처럼 있고, (A)B 처럼 A와 B자리를 만들자.
남은 N−1 쌍 중, A에 K쌍을 넣으면 B에는 N−1−K쌍이 존재하게 된다.
이는 곧 CK⋅CN−1−K 를 의미하며, 전체를 모두 합치면
Cn=k=0∑n−1CkCn−1−k 이 된다.
이건 꼭 괄호라는 매개체만 적용되는 것이 아닌, 스택과 관련된 총 경우의 수라든가,
가령 Dyck words 같은 문제라든지,
다음과 같이 스택 문제로 환원될 수 있는 문제 같은 것들이 있다.

/ 모양과 \ 모양을 이용해 산을 만들 때 모양의 가지 수
다각형 분할

선분끼리 겹치지 않고 n각형일 때, n−2개의 영역으로 나누는 경우의 수
위 문제를 생각해보면, 6각형이므로 꼭짓점들을 p1, ⋯ p6 이라 한다면, pi와 pj를 이어 공간을 나눴을 때
(∣i−j∣>1),
나뉘어진 두 다각형에 있는 꼭짓점들의 개수가 k+2, 6−k+2가 됨이 보인다.
예를 들어 육각형의 두 인접하지 않는 꼭짓점을 이어 삼각형과 오각형으로 분할할 수 있다.
C6=C3⋅C5+C4⋅C4+C5⋅C3 가 되고,
여기서 2씩 빼면 카탈란 수의 점화식이 나옴을 볼 수 있을 것이다.
악수 문제
BOJ 17268, BOJ 1670
각 꼭짓점들이 짝지어 겹치지 않는 경우가 몇개가 나오는지를 묻는 문제이다.
동일하게 카탈란 수로 풀 수 있다.
N,N grid에서 대각선을 넘어가지 않고 한 쪽 영역만 사용해서 이동하는 최단경로 문제

이 문제에서 CN=2n+11(n2n) 을 증명할 것이다.
위 문제에서 대각선을 넘어가지 않고 한쪽 영역만으로 반대쪽 대각선 꼭짓점에 도달하는 경로의 수는 앞서 다루었던 문제들로 치환될 수 있기 때문에 이러한 경로의 개수가 2n+11(n2n) 라고 증명하면 된다. (전단사 증명)
exceedance = 대각선 위에있는 수직경로의 개수
라고 하자.
예를 들어 다음과 같은 그림은 exceedance가 5이다.

만약 exceedance가 0이 아닌 어떤 경로가 있다면, 다음과 같은 알고리즘을 통해 exceedance를 1 줄여줄 수 있다.
- 왼쪽 아래에서 시작해 diagonal(대각선 그어져있는 것) 위에 도달할 때 까지 진행
- digonal을 두 번째로 touch 할 때, 그 때의 x좌표를 X라 하자.
- [0,X−1]와 [X,N] 구간의 경로를 Swap 한다.

exceedance는 3→2 이다.
이것이 성립하는 이유는 일단 앞으로간 [X,N]에서의 exceedance는 변함이 없고
[X,X]를 시작해[N,N] 을 거치던 경로가 [0,0]에서 시작해 [N−X,N−X]로 옮겨진 것이기 때문이다.
뒤로간 [0,X−1] 의 경로는 항상 →가(Figure의 검은색 화살표) 하나 먼저 붙은 채로 X에서 다시 시작하기 때문에 exceedance는 1 감소한다.
이로 인해 얻을 수 있는 결론은,
exceedancen=exceedancen−1=⋯=exceedance0
이다.
따라서 n+1 개의 서로 다른 exceedance를 가지는 경로들의 개수가 모두 같고, 총 경로의 개수는 (n2n) 이기 때문에,
Cn=n+11(n2n)
임이 증명된다.
구현
O(N2)
O(N2)부터 살펴보자.
BOJ 10422 를 풀어보자.
const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
void solve() {
int t;
cin >> t;
vector<ll> dp(2501);
dp[0] = 1;
for (int i = 1; i <= 2500; i++) {
for (int j = 0; j < i; j++) {
int k = i - 1 - j;
dp[i] = md(dp[i] + dp[j] * dp[k]);
}
}
while (t--) {
int n;
cin >> n;
if (n & 1) cout << 0 << endl;
else cout << dp[n / 2] << endl;
}
}
와 같이 풀 수 있다. 식을 그대로 가져다 써주기만 하면 된다.
O(N)
Cn≡n+11(n2n)≡(n+1)!⋅n!(2n)! (mod p)
이제 이 식을 이용해보자.
우리가 먼저 계산해야 할건 2n 까지에 대한 값이다.
vi f(5001);
f[0] = 1;
for (int i = 1; i <= 5000; i++) f[i] = md(f[i - 1] * i);
이제 (n+1)!⋅n! 의 모듈러 역원을 곱해주기만 하면 된다.
이는 페르마의 소정리
ap−1≡1 (mod p)(p∤a)
를 이용하여 모듈러 역원의 정의는 a 에 대해 ax≡1 를 만족하는 x 이므로
a⋅ap−2≡1 (mod p) ⇒x=ap−2 이용해서 푼다.
const ll mod = 1e9 + 7;
inline ll md(ll x) { return md(mod, x); }
ll pw(ll a, ll b) {
ll ret = 1;
while (b) {
if (b & 1) ret = md(ret * a);
a = md(a * a);
b >>= 1;
}
return ret;
}
void solve() {
int t;
cin >> t;
vector<ll> f(5001);
f[0] = 1;
for (int i = 1; i <= 5000; i++) f[i] = md(f[i - 1] * i);
while (t--) {
int n;
cin >> n;
if (n & 1) {
cout << 0 << endl;
continue;
}
n >>= 1;
ll ans = f[n * 2];
ll denomiator = md(f[n + 1] * f[n]);
ll inverse = pw(denomiator, mod - 2);
cout << md(ans * inverse) << endl;
}
}
이렇게 다른 시간복잡도로 풀었을 때 결과는 다음과 같다.

Comments