Catalan NumberPermalink

카탈란 수는 n+1n+1개의 인수의 곱을 결합법칙이 성립하지 않을 때 표현하는 경우의 수이다.

Cn\quad \color{salmon} C_n와 같이 쓴다.

예시로, n=3n=3이면 다음과 같이 5개이다.

  1. (((ab)c)d)(((ab)c)d)
  2. ((a(bc))d)((a(bc))d)
  3. (a((bc)d))(a((bc)d))
  4. (a(b(cd)))(a(b(cd)))
  5. ((ab)(cd))((ab)(cd))

두 개씩만 인수들을 묶는다.

이 숫자가 재밌는 이유는, 위와 같이 겉보기엔 단순해보이는 정의가 나타내는 이 수가 굉장히 다양한 문제의 해답으로 표현되기 때문이다.

일반항Permalink

C0C_000이라고 한다면,

Cn=1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, \quad C_n=1,~1,~2,~5,~14,~42,~132,~429,~1430,~4862,~\cdots

와 같이 증가한다.

Cn=1n+1(2nn)=(2n)!(n+1)!n!\quad C_n= \dfrac 1{n+1} \dbinom{2n}n= \dfrac{(2n)!}{(n+1)!\cdot n!}

이 일반항은 O(N+logp)O(N+\log p)이 걸리지만, 실제로 수가 커져서 modular inverse를 계산하게끔 나머지를 소수로 주어지는 문제가 아니라면 써먹을 수 없는 방법이다.

Cn=2(2n1)n+1Cn1(n1)\quad C_n=\dfrac{2(2n-1)}{n+1}C_{n-1} \small (n\geq1)

이 일반항은 O(Nlogp)O(N \log p) 정도가 걸린다.

Cn=k=0n1CkCn1k=C0Cn1+C1Cn2+\quad C_n=\displaystyle\sum_{k=0}^{n-1}C_k C_{n-1-k}=C_0 \cdot C_{n-1} + C_1 \cdot C_{n-2} + \cdots

O(N2)O(N^2) 이지만 이것이 문제에서 가장 흔하다.

Applicable ProblemsPermalink

위에서 들었던 예시대로 문제를 풀어보자.

괄호, 스택 문제Permalink

BOJ 10422

이 문제는 O(N2)O(N^2)로 해결할 수 있다.

괄호가 1쌍이라면, ()() 정답은 1개이다.

2쌍이라면 ()()()(), (())(()) 2개이다.

그 이후부터 생각을 해보자.

이번에 추가해야 할 괄호 한 쌍이 ()() 처럼 있고, (A)B(A)B 처럼 AABB자리를 만들자.

남은 N1N-1 쌍 중, AAKK쌍을 넣으면 BB에는 N1KN-1-K쌍이 존재하게 된다.

이는 곧 CKCN1KC_{K} \cdot C_{N-1-K} 를 의미하며, 전체를 모두 합치면

Cn=k=0n1CkCn1k\quad C_n=\displaystyle\sum_{k=0}^{n-1}C_k C_{n-1-k} 이 된다.

이건 꼭 괄호라는 매개체만 적용되는 것이 아닌, 스택과 관련된 총 경우의 수라든가,

가령 Dyck words 같은 문제라든지,

다음과 같이 스택 문제로 환원될 수 있는 문제 같은 것들이 있다.

image

/ 모양과 \ 모양을 이용해 산을 만들 때 모양의 가지 수

다각형 분할Permalink

선분끼리 겹치지 않고 nn각형일 때, n2n-2개의 영역으로 나누는 경우의 수

위 문제를 생각해보면, 6각형이므로 꼭짓점들을 p1,  p6p_1,~\cdots~p_6 이라 한다면, pip_ipjp_j를 이어 공간을 나눴을 때 (ij>1)\small(\vert i - j \vert > 1), 나뉘어진 두 다각형에 있는 꼭짓점들의 개수가 k+2, 6k+2k+2,~6-k+2가 됨이 보인다.

예를 들어 육각형의 두 인접하지 않는 꼭짓점을 이어 삼각형과 오각형으로 분할할 수 있다.

C6=C3C5+C4C4+C5C3\quad C_6=C_3 \cdot C_5 + C_4 \cdot C_4 + C_5 \cdot C_3 가 되고,

여기서 2씩 빼면 카탈란 수의 점화식이 나옴을 볼 수 있을 것이다.

악수 문제Permalink

BOJ 17268, BOJ 1670

각 꼭짓점들이 짝지어 겹치지 않는 경우가 몇개가 나오는지를 묻는 문제이다.

동일하게 카탈란 수로 풀 수 있다.

N,NN, N grid에서 대각선을 넘어가지 않고 한 쪽 영역만 사용해서 이동하는 최단경로 문제Permalink

image

이 문제에서 CN=12n+1(2nn)C_N=\dfrac 1{2n+1} \dbinom{2n}n 을 증명할 것이다.

위 문제에서 대각선을 넘어가지 않고 한쪽 영역만으로 반대쪽 대각선 꼭짓점에 도달하는 경로의 수는 앞서 다루었던 문제들로 치환될 수 있기 때문에 이러한 경로의 개수가 12n+1(2nn)\dfrac 1{2n+1} \dbinom{2n}n 라고 증명하면 된다. (전단사 증명)

exceedance = 대각선 위에있는 수직경로의 개수

라고 하자.

예를 들어 다음과 같은 그림은 exceedance가 5이다.

만약 exceedance가 00이 아닌 어떤 경로가 있다면, 다음과 같은 알고리즘을 통해 exceedance를 11 줄여줄 수 있다.

  1. 왼쪽 아래에서 시작해 diagonal(대각선 그어져있는 것) 위에 도달할 때 까지 진행
  2. digonal을 두 번째로 touch 할 때, 그 때의 xx좌표를 XX라 하자.
  3. [0,X1][0,\,X-1][X,N][X,\,N] 구간의 경로를 Swap 한다.

exceedance는 323\to2 이다.

이것이 성립하는 이유는 일단 앞으로간 [X,N][X,\,N]에서의 exceedance는 변함이 없고

[X,X][X,\,X]를 시작해[N,N][N,\,N] 을 거치던 경로가 [0,0][0,\,0]에서 시작해 [NX,NX][N-X,\,N-X]로 옮겨진 것이기 때문이다.

뒤로간 [0,X1][0,\,X-1] 의 경로는 항상 \to가(Figure의 검은색 화살표) 하나 먼저 붙은 채로 XX에서 다시 시작하기 때문에 exceedance는 11 감소한다.

이로 인해 얻을 수 있는 결론은,

exceedancen=exceedancen1==exceedance0 \quad exceedance_n=exceedance_{n-1}=\cdots=exceedance_0

이다.

따라서 n+1n+1 개의 서로 다른 exceedance를 가지는 경로들의 개수가 모두 같고, 총 경로의 개수는 (2nn)\color{salmon} \dbinom{2n}n 이기 때문에,

Cn=1n+1(2nn) C_n=\dfrac1{n+1}\dbinom{2n}n

임이 증명된다.

구현Permalink

O(N2)O(N^2)Permalink

O(N2)O(N^2)부터 살펴보자.

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)O(N)Permalink

Cn1n+1(2nn)(2n)!(n+1)!n!  (mod p)\quad C_n \equiv \dfrac 1{n+1} \dbinom{2n}n \equiv \dfrac{(2n)!}{(n+1)!\cdot n!}~~\small(mod~p)

이제 이 식을 이용해보자.

우리가 먼저 계산해야 할건 2n2n 까지에 대한 값이다.

vi f(5001);  
f[0] = 1;  
for (int i = 1; i <= 5000; i++) f[i] = md(f[i - 1] * i);

이제 (n+1)!n!(n+1)! \cdot n! 의 모듈러 역원을 곱해주기만 하면 된다.

이는 페르마의 소정리

ap11  (mod p)(pa) a^{p-1} \equiv 1~~(mod~p)\\ \small (p \nmid a)

를 이용하여 모듈러 역원의 정의는 aa 에 대해 ax1ax\equiv1 를 만족하는 xx 이므로

aap21  (mod p) x=ap2a\cdot a^{p-2}\equiv1~~(mod~p)\ \Rightarrow x=a^{p-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