3
$\begingroup$

I want to prove combinatorially that $n {2n \choose n} = (n+1) {2n \choose n+1} $. I have noticed that ${2n \choose n}$ is the number of ways walking only north or east in a square from a corner to another along the sides and ${2n \choose n+1} $ in a rectangle with $n-1 \times n+1$. Another approach I had was noting that the left-hand side can be modeled as the numbers of way we can choose $n$ balls from $2n$ balls and paint exactly one of these. The right-hand side is the number of ways choosing $n+1$ balls and painting exactly one of these (among $2n$ balls). However, I cannot quite realize why they must be equal. Someone have an explanation?

$\endgroup$
4
$\begingroup$

Using your second description, here's the bijection. Say you've chosen $n$ balls and painted exactly one. Make a new pile, where you take the $n$ balls you didn't choose, and add to them the one you painted. Now you've chosen $n + 1$ balls, and painted exactly one.

$\endgroup$
1
  • $\begingroup$ I also thought of this, but I was not quite sure if I was right. Thank you! $\endgroup$ – user30523 May 1 '15 at 17:34
1
$\begingroup$

Take your first example of a square and a rectangle.

You start with the bottom left corner of the rectangle and you move $n+1$ times right and $n-1$ times up to get to its top left corner.

Choose one of the right moveד and make it an up move and you will end up in the top right corner of the square.

Hence, we showed that by multiplying the number of combinations to reach the top right corner of the rectangle by $n+1$ we get the number of combinations to reach the top right hand corner of the square.

$\endgroup$
1
  • $\begingroup$ You'll end up in the top right corner of the square, with a distinguished up move out of the $n$ up moves. So you're getting the number of ways to reach the top right corner of the square times $n$, which is good because $(n+1){2n \choose n+1} = n{2n \choose n}$ is what you want. $\endgroup$ – aes May 1 '15 at 18:48

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.