Is there a unique definition of Catalan numbers?

Question

So I am studying Catalan numbers, and I see there is no one single definition of Catalan numbers .

However, I was wondering how can you explain the Catalan number formula combinatorically ?

so the nth Catalan number can be found using the formula $$C_n = {2n \choose n} - {2n \choose n +1}$$

So ${2n \choose n}$ is the numbers of ways to choose $n$ objects from a set of $2n$ objects.

and ${2n + 1 \choose n+1}$ objects is the number of ways to choose $n+1$ objects from $2n+1$ objects .

Now how what can we say about $${2n \choose n} - {2n \choose n +1}$$

I want to explain it using words.

Also Is it true that Euler first found the Catalan Recurrence Relation $$C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}\tag{0}$$

and The formula $$C_n = \frac{1}{n+1} {2n \choose 2}$$ was found much later ?

And what is the most important application for Catalan numbers?

Answer 1

There are many, many combinatorial definitions of the Catalan numbers (see rogerl's comment), but the most common might be that $C_n$ counts the number of lattice paths from $(0,0)$ to $(n,n)$ that only take unit step right and up, and never cross the diagonal line $y = x$ (but they are allowed to touch the diagonal line). There is not a unique definition of Catalan numbers because all of the various combinatorial definitions are equivalent to each other, so which one you take as your definition is a stylistic preference. One of the beautiful aspects of the Catalan numbers is that they have so many interesting interpretations.

For example, $C_4 = 5$ and the five lattice paths can be encoded by a sequence of $R$'s (for a step right) and $U$'s (for a step up). The five Catalan paths in this case are $RRRUUU$, $RRURUU$, $RRUURU$, $RURRUU$, and $RURURU$. Notice that in the code for each path, when reading from left to right, I will have always read more $R$'s than $U$'s at any point in the reading. This reflects the fact that if at any point the path has taken more up steps than steps to the right, it will have crossed the diagonal line $y = x$. (These codes are called "ballot sequences" and are another common combinatorial definition of Catalan numbers.)