3
$\begingroup$

Is there any combinatorial interpretation or bijective proof for this identity $$2C_n=4{2n \choose n}-{2n+2 \choose n+1}$$ where $C_n$ is the sequence of Catalan numbers?

$\endgroup$
0
6
$\begingroup$

There is an obvious bijective proof of the identity $$ 2 \binom{2n}{n} + 2 \binom{2n}{n + 1} = \binom{2n+2}{n+1}$$ and also a bijective proof of $$ 2\binom{2n}{n} - 2 \binom{2n}{n+1} = 2C_n,$$ see the paragraph "second proof" in the wiki page. By combining the two, you get a bijective proof of your identity, in the form $$ 4 \binom{2n}{n} =\binom{2n+2}{n+1} + 2C_n .$$

$\endgroup$
1
$\begingroup$

In the wikipedia page on Catalan numbers there is the following:

"There are many counting problems in combinatorics whose solution is given by the Catalan numbers. The book Enumerative Combinatorics: Volume 2 by combinatorialist Richard P. Stanley contains a set of exercises which describe 66 different interpretations of the Catalan numbers."

I guess it is a good place to look for an answer.

$\endgroup$

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.