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?