카탈란 수와 괄호 쌍 문제

 

카탈란 수(catalan number)와 괄호 쌍 문제

 

 

 

 

 

정상 괄호 쌍 또는 비정상 괄호 쌍을 구하는 문제가 나오면 카탈란 수 공식을 이용합니다.

여기에서 n은 괄호쌍의 수를 의미합니다.

 

(1) 모든 경우 수                 = 2n C n = (2n)!/((2n-n)!*n!)

(2) 비정상 괄호 쌍 경우 수   = 2n C n+1 = (2n)!/((2n-n-1)!*(n+1)!)

(3) 정상 괄호 쌍 경우 수      = 모든 경우 - 비정상 경우 = (1)식 - (2)식

 

[참고] 2n C n 공식은 조합 경우의 수를 참조하세요.

 

1) 4개 괄호 쌍이 존재할 때 비정상적인 괄호 쌍의 수는 몇 개인가?  (((( ))))

 

n이 4인 경우이므로

2n C n+1 = 8 ! / 3!5! = 56 가지

 

2) 4개 괄호 쌍이 존재할 때  정상적인 괄호 쌍의 수는 몇 개인가?   (((( ))))

모든 괄호 쌍은 8! / 4!4! = 70 가지

비정상 괄호 쌍은 1)처럼 56 가지

그러므로 정상 괄호 쌍은 70 - 56이므로 14가지 존재한다.  

 

또는 정상 괄호쌍은 다음 수식으로 직접 구할 수 있습니다.

 

(2*n)! / (n)! / (n+1)!

 

정상 괄호쌍을 구하는 C++ 코드는 다음과 같습니다. 

 

#include <iostream>

using namespace std;

 

long double f(int n) {
    long double f=1;
    if(n<=1)
        return 1;
   
    for(int i=2; i<=n; i++)
        f*=i;
    return f;   
}

 

long double solution(int n) {
    return f(2*n) / f(n) / f(n+1);
}

 

int main() {
    for(int i=1; i<10; i++)
       cout << solution(i) << endl;
  
    return 0;  
}

 

<이상>