Catalan Number

http://en.wikipedia.org/wiki/Catalan_number

組合數學上很重要的數列

1, 1, 2, 5, 14, 42, 132, 429 ...

這個特殊的遞迴式很好用

#!/usr/bin/python

c = [1, 1, 1]
for _ in range (3, 10+1):
    # f(n+1) = f(n) * (4n-6 / n)
    c.append(c[_-1] * (4*(_-1) - 6) / (_-1))

print c[2:]

# [1, 1, 2, 5, 14, 42, 132, 429, 1430]