Catalan Numbers(2016)
The Catalan numbers are a sequence of natural numbers that occur in various problems in combinatorial mathematics. For example, the number of expressions containing \(n\) valid pairs of parentheses is the \(n\)th Catalan number. Suppose you have a grid of \(n \times n\) squares, the \(n\)th Catalan number represents the number of paths with a length of \(2n\) that lead from the upper left corner to the lower right corner without intersecting the diagonal dotted line running from the upper left to the lower right. Later in the page, we will derive explicit formulas for the Catalan numbers in two different ways.