Python calculating Catalan Numbers

Question

I have code which is calculating catalan numbers with method of Binominal Coefficients.

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))

I have a "nan" result when i try to calculate Catalan number which n is more than 510. Why this is happening? And how can i solve it?

You get `nan` because `BinominalCoefficient(1022, 511)` returns `inf`. — James Pringle, Jul 16 '15 at 16:34
Are you using Python 3? If so use integer division `//` to avoid floats (you don't need them for this calculation anyway). — Alex Riley, Jul 16 '15 at 16:38
What python version are you using? I get correct results in both python 2.6.6 as well as python 3.4.3 — Anand S Kumar, Jul 16 '15 at 16:39

xnx · Accepted Answer · 2015-07-16T16:42:38.857

I assume you're using Python 3.

Your res /= (i + 1) should be res //= (i + 1) to force integer arithmetic:

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))

returns

2190251491739477424254235019785597839694676372955883183976582551028726151813997871354391075304454574949251922785248583970189394756782256529178824038918189668852236486561863197470752363343641524451529091938039960955474280081989297135147411990495428867310575974835605457151854594468879961981363032236839645

You get nan because the divison /= in Python 3 returns a float which overflows to inf.

score 2 · Answer 2 · answered Jun 01 '19 at 11:21

2

In addition to xnx's answer, note that starting Python 3.8, with the addition of math.comb (binomial coefficient) in the standard library, we can also calculate Catalan numbers as such:

import math

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

catalan(511) # 2.1902514917394773e+303

answered Jun 01 '19 at 11:21

Xavier Guihot

54,987
21
291
190

1

Notice that this solution is bounded by the float bounds. The maximal Catalan number that can be calculated this way is catalan(519), for catalan(520) you'll get OverflowError – user107511 Aug 03 '21 at 13:39

Python calculating Catalan Numbers

2 Answers2