Catalan number

The Catalan numbers are an integer sequence. They are named for Eugène Charles Catalan, who found the relationship between these numbers and parentheses. They were previously described by Mingantu in 1731 and Leonhard Euler in 1757.

The first ten Catalan numbers are

1, 1, 2, 5, 42, 132, 429, 1430, 4862, 16796... (sequence A000108 in the OEIS)

The Catalan numbers can be written in terms of the binomial coefficient: $${\displaystyle C_{n}={\frac {1}{2n+1}}{\binom {2n+1}{n}}={\binom {2n}{n}}-{\binom {2n}{n+1}}}$$ They satisfy two significant recurrence relations, starting from ${\displaystyle C_{0}=1}$: $${\displaystyle C_{n+1}=\sum _{k=0}^{n}C_{k}C_{n-k}={\frac {2(2n+1)}{n+2}}C_{n}}$$