Python计算卡特兰数

Question

我有一段用二项式系数法计算卡特兰数的代码。

def BinominalCoefficient(n,k):
    res = 1;
    if (k > n - k):
        k = n - k
    for i in range(k):
        res *= (n - i)
        res /= (i + 1)
    return res
def CatalanNumbers(n):
   c = BinominalCoefficient(2*n, n)
   return (c//(n+1))
print (CatalanNumbers(510))

当我尝试计算大于510的卡特兰数时，结果显示为“nan”。这是怎么回事？我该如何解决？

- Reodont

---

你得到了 nan，因为 BinominalCoefficient(1022, 511) 返回了 inf。 - James Pringle

你正在使用Python 3吗？如果是的话，请使用整数除法//来避免浮点数（无论如何，你都不需要它们进行这个计算）。 - Alex Riley

你使用的是哪个Python版本？我在Python 2.6.6和Python 3.4.3中都能得到正确的结果。 - Anand S Kumar

我正在使用Python 3.4.3。 - Reodont

Answer 1

我假设您正在使用Python 3。

您的res /= (i + 1)应该改为res //= (i + 1)以强制使用整数算术：

def BinominalCoefficient(n,k):
    res = 1
    if (k > n - k):
        k = n - k
    for i in range(k):
        res *= (n - i)
        res //= (i + 1)
    return res
def CatalanNumbers(n):
   c = BinominalCoefficient(2*n, n)
   return (c//(n+1))
print (CatalanNumbers(511))

返回

2190251491739477424254235019785597839694676372955883183976582551028726151813997871354391075304454574949251922785248583970189394756782256529178824038918189668852236486561863197470752363343641524451529091938039960955474280081989297135147411990495428867310575974835605457151854594468879961981363032236839645

因为Python 3中除以/=会返回一个浮点数，导致结果溢出成为inf，所以你得到了nan。

- xnx

Answer 2

除了xnx的回答外，请注意从Python 3.8开始，标准库中添加了math.comb（二项式系数），我们也可以这样计算卡特兰数：

最初的回答：

import math

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

catalan(511) # 2.1902514917394773e+303

- Xavier Guihot

---

请注意，此解决方案受浮点边界限制。可以通过此方法计算的最大卡特兰数为catalan(519)，计算catalan(520)将会出现OverflowError。 - user107511