Catalan Number

Very important number series occurring in combinatorics: https://en.wikipedia.org/wiki/Catalan_number

Recurrence relation:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_0 = 1 }

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{n+1} = \sum_{i=0}^{n} C_{i} C_{n-i} }

Formula:

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://en.wikipedia.org/api/rest_v1/":): {\displaystyle C_{n} = \dfrac{(2n)!}{(n+1)! n!} }

More links:

• Wikipedia link (also above): https://en.wikipedia.org/wiki/Catalan_number
• geeks for geeks, focusing on programming implementations (non-recursive and recursive): http://www.geeksforgeeks.org/program-nth-catalan-number/
• interview repo on github: https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/CountNumberOfTreesInBST.java