Catalan numbers: Difference between revisions

'''Solution'''

'''Direct definition'''

[[File:Fōrmulæ - Catalan numbers 01.png]]

[[File:Fōrmulæ - Catalan numbers 02.png]]

'''Direct definition (alternative)'''

The expression <math>\frac{(2n)!}{(n+1)!\,n!}</math> turns out to be equals to <math>\prod_{k=2}^{n}\frac{n + k}{k}</math>

[[File:Fōrmulæ - Catalan numbers 03.png]]

(same result)

'''No directly defined'''

Recursive definitions are easy to write, but extremely inefficient (specially the first one).

Because a list is intended to be get, the list of previous values can be used as a form of memoization, avoiding recursion.

The next function make use of the "second" form of recursive definition (without recursion):

[[File:Fōrmulæ - Catalan numbers 04.png]]

[[File:Fōrmulæ - Catalan numbers 05.png]]

(same result)