파이썬(Python)으로 이항 계수를 활용해 카탈란 수 계산하는 방법

카탈란 수(Catalan Number)는 조합론의 다양한 문제에 등장하는 유명한 수열입니다. 이 수열은 올바른 괄호 쌍의 개수, 이진 트리의 경우의 수 등 여러 조합 문제에서 나타나며, 이항 계수를 이용하면 매우 간단하게 계산할 수 있습니다.

카탈란 수의 n번째 항은 다음 공식으로 정의됩니다.

C(n) = C(2n, n) / (n + 1)

따라서 파이썬으로 카탈란 수를 계산하려면 먼저 이항 계수를 구하는 함수를 작성해야 합니다.

예제 코드

def binomialCoefficient(n, k):
    # C(n, k) 계산 최적화
    if (k > n - k):
        k = n - k
    coeff = 1
    for i in range(k):
        coeff *= (n - i)
        coeff /= (i + 1)
    return coeff

def catalan(n):
    return binomialCoefficient(2*n, n) / (n + 1)

for i in range(11):
    print(catalan(i))

실행 결과

위 코드를 실행하면 다음과 같이 0번째부터 10번째까지의 카탈란 수가 출력됩니다.

1.0
1.0
2.0
5.0
14.0
42.0
132.0
429.0
1430.0
4862.0
16796.0

코드 상세 설명

1. binomialCoefficient 함수

이 함수는 이항 계수 C(n, k)를 효율적으로 계산합니다. 이항 계수의 대칭성(C(n, k) = C(n, n-k))을 활용하여 k가 n-k보다 클 경우 k를 n-k로 교체함으로써 반복 횟수를 줄일 수 있습니다. 이후 곱셈과 나눗셈을 번갈아 수행해 중간값이 불필요하게 커지는 것을 방지합니다.

2. catalan 함수

카탈란 수의 공식인 C(n) = C(2n, n) / (n + 1)을 그대로 구현한 함수입니다. 2n개 중 n개를 선택하는 이항 계수 값을 n + 1로 나누어 카탈란 수를 구합니다.

3. 참고 사항

위 코드에서는 실수 나눗셈 연산자(/)를 사용했기 때문에 결과가 소수점 형태(float)로 출력됩니다. 정수 결과를 얻고 싶다면 나눗셈 부분을 정수 나눗셈(//)으로 변경하거나, 파이썬 3.8 이상에서 제공하는 math.comb() 함수를 활용해 다음과 같이 더 간결하게 작성할 수도 있습니다.

import math

def catalan(n):
    return math.comb(2 * n, n) // (n + 1)

이처럼 이항 계수 기반 접근 방식은 반복문 한 번으로 계산이 가능해 재귀적 정의를 사용하는 방법보다 훨씬 빠르고 효율적입니다.