Prove that $\frac{\binom{2n}{n}}{n+1}$ is an integer.

Question

Prove that $\frac{\binom{2n}{n}}{n+1}$ is an integer.

I know a method using algebraic manipulation to prove this statement but can anyone tell me (even a slight hint would do) how to prove this using a combinatorial argument?

Answer 1

At stated in the comments, these are the Catalan numbers. On the Wikipedia article, some combinatorial interpretations are given. My favourite proof is to solve Bertrand's ballot problem and to use it to find a formula for the Catalan recurrence. This method is presented on p.13 of Four Proofs of the Ballot Theorem by Renault.

If you look up Richard Stanley, you'll find that the fellow has been collecting for years combinatorial problems whose solution is the Catalan numbers. He is famous, among other reasons, for having dozens of exercises that boil down to the Catalan numbers in his book, Enumerative Combinatorics. In the end in 2015, he published a book on it, Catalan Numbers, which has over 200 objects that can be counted using the Catalan numbers. On this web page, he wrote that

The material I have gathered on Catalan numbers was collected into a monograph. This will be the final version of my material on Catalan numbers. The current web page will not be updated.