Interpretation for identity with binomial coefficients

  • #1
299
12

Main Question or Discussion Point

I am looking for a counting interpretation to make the following identity evident:

[tex]\sum_{k=0}^{n-j}(-1)^k\binom{j-1+k}{j-1}\binom{n}{j+k} = 1[/tex]

The form of it looks like inclusion-exclusion. The sum is 1, more or less independent of j. So that makes me think it would be something like "how many ways can you toss a coin n times, getting heads on the first j tosses and tails on the rest?", which obviously happens in one way. The problem is, I don't see how the left side of the equation can be interpreted that way.

Thanks in advance.
 

Answers and Replies

  • #2
160
21
The easiest way to deal with identities having alternating signs is to use the "involution principle", which is not much more than a fancy name for moving the negative terms to the other side. (See Stanley, Enumerative Combinatorics, vol. 1, section 2.6.)

The quantity [tex]\binom{n}{j+k}\binom{j-1+k}{j-1}[/tex] counts the number of ways to take a row of ##n## balls and choose ##j+k## of them to paint. Of these, you paint the rightmost one red. Then, of the others, you paint ##j-1## blue and ##k## green.

You can then construct an (almost) "sign-reversing involution" on this set -- basically, this means a bijection between the paintings where k is odd and the paintings where k is even. One way to do this is by starting at the red ball and going to the left one ball at a time until you find a ball that is either green or unpainted. If it's green, you remove the paint; if it's unpainted, you paint it green.

As I said, this is not quite a sign-reversing involution because there is one case where it isn't defined. If, from the left, the row starts with ##j-1## blue balls and then a red ball, there is no way to follow the above instruction.

But this is actually a good thing. After all, there was that "1" floating around. So the bijection handles all the cases except for one; to compensate for this, you have to add 1 to the other side. And that gives you the identity you were looking for.

Another way of looking at this is that the sign-reversing involution tells you how to cancel out paintings in pairs, where 1 element of each pair has k even and the other has k odd. Everything is canceled out except for the one exceptional painting, and so after the cancellation you have just 1 left, which is the right side.
 
  • #3
299
12
Thank you, eigenperson! That was a first rate solution and explanation. I encountered that sum while trying to find an expected value in the broken-stick model here, and couldn't come up with an approach for it.

Thanks again :)
 

Related Threads on Interpretation for identity with binomial coefficients

  • Last Post
Replies
3
Views
3K
Replies
3
Views
756
  • Last Post
Replies
4
Views
696
  • Last Post
Replies
5
Views
492
  • Last Post
Replies
5
Views
3K
Replies
5
Views
1K
Replies
2
Views
1K
Replies
2
Views
563
  • Last Post
Replies
1
Views
611
Top