1
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ See here for a discussion of the definition you give at the start of your post. Elsewhere in the article things that are counted by the Catalan numbers are given; you should also look at Enumerative Combinatorics v.2. $\endgroup$
    – rogerl
    Dec 1, 2015 at 21:27
  • $\begingroup$ Chapter 2 of Catalan Numbers by Richard P. Stanley gives 214 (!) combinatorial interpretations of the Catalan numbers. $\endgroup$
    – user940
    Dec 1, 2015 at 22:04

1 Answer 1

1
$\begingroup$

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.)

$\endgroup$
2
  • $\begingroup$ How can I explain $${2n \choose n} - {2n+1 \choose n +1}$$ in combinatorial terms , It is the set of what ? $\endgroup$
    – alkabary
    Dec 1, 2015 at 21:47
  • $\begingroup$ $2n \choose n$ counts the set of all lattice paths from $(0,0)$ to $(n,n)$ using unit steps up and to the right, while $2n+1 \choose n+1$ counts the set of all such lattice paths that do cross the diagonal $y = x$. See the wikipedia article in rogerl's comment for the details. It's got everything you need and is written quite well. $\endgroup$ Dec 1, 2015 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.