Catalan numbers

You are encouraged to solve this task according to the task description, using any language you may know.


Catalan numbers are a sequence of numbers which can be defined directly:






C

n


=


1

n
+
1






(



2
n

n


)



=



(
2
n
)
!


(
n
+
1
)
!

n
!





 for 

n
≥
0.


{\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}={\frac {(2n)!}{(n+1)!\,n!}}\qquad {\mbox{ for }}n\geq 0.}


Or recursively:






C

0


=
1


and



C

n
+
1


=

∑

i
=
0


n



C

i




C

n
−
i




for 

n
≥
0
;


{\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n+1}=\sum _{i=0}^{n}C_{i}\,C_{n-i}\quad {\text{for }}n\geq 0;}


Or alternatively (also recursive):






C

0


=
1


and



C

n


=



2
(
2
n
−
1
)


n
+
1




C

n
−
1


,


{\displaystyle C_{0}=1\quad {\mbox{and}}\quad C_{n}={\frac {2(2n-1)}{n+1}}C_{n-1},}




Task

Implement at least one of these algorithms and print out the first 15 Catalan numbers with each.

Memoization   is not required, but may be worth the effort when using the second method above.



Related tasks

Catalan numbers/Pascal's triangle
Evaluate binomial coefficients


from math import factorial
import functools
 
 
def memoize(func):
    cache = {}
 
    def memoized(key):
        # Returned, new, memoized version of decorated function
        if key not in cache:
            cache[key] = func(key)
        return cache[key]
    return functools.update_wrapper(memoized, func)
 
 
@memoize
def fact(n):
    return factorial(n)
 
 
def cat_direct(n):
    return fact(2 * n) // fact(n + 1) // fact(n)
 
 
@memoize
def catR1(n):
    return 1 if n == 0 else (
        sum(catR1(i) * catR1(n - 1 - i) for i in range(n))
    )
 
 
@memoize
def catR2(n):
    return 1 if n == 0 else (
        ((4 * n - 2) * catR2(n - 1)) // (n + 1)
    )
 
 
if __name__ == '__main__':
    def pr(results):
        fmt = '%-10s %-10s %-10s'
        print((fmt % tuple(c.__name__ for c in defs)).upper())
        print(fmt % (('=' * 10,) * 3))
        for r in zip(*results):
            print(fmt % r)
 
    defs = (cat_direct, catR1, catR2)
    results = [tuple(c(i) for i in range(15)) for c in defs]
    pr(results)