Pythonで二項係数を使ってカタラン数を計算する方法

カタラン数（Catalan number）は、組み合わせ論においてさまざまな場面で登場する有名な数列です。例えば、正しく対応した括弧列の数や、n個のノードからなる二分木の構成方法の数などを表します。

カタラン数は二項係数を用いて次のように定義できます。

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

つまり、Pythonでカタラン数を求めるには、まず二項係数 C(n, k) を計算する関数を用意し、その結果を (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))

コードのポイント

• binomialCoefficient 関数では、k を n-k と比較して小さい方に置き換えることで、ループ回数を減らし計算を効率化しています。
• 乗算と除算を交互に行うことで、中間値が極端に大きくなるのを防いでいます。
• catalan 関数は、定義式「C(2n, n) / (n + 1)」をそのまま実装したものです。

実行結果

このコードを実行すると、0番目から10番目までのカタラン数が出力されます。

1.0
1.0
2.0
5.0
14.0
42.0
132.0
429.0
1430.0
4862.0
16796.0

補足：整数として出力したい場合

上記のコードでは除算により結果が浮動小数点数（float型）になります。整数として得たい場合は、catalan 関数内で int() に変換するか、Python 3.8以降で利用できる math.comb を使うと簡潔に書けます。

import math

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

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

このように、二項係数の計算を組み合わせることで、カタラン数を簡単かつ効率的に求めることができます。