Combinatorical proof regarding multinomial coefficients

Question

Okay, so combinatorics isn't exactly my strong suit, so bear with me.

I'm asked to prove the following combinatorically:

If n is a nonnegative integer and k is an integer, then

$$\sum_j {n \choose j,k,n-j-k} = 2^{n-k} {n \choose k}$$

I do know that the above multinomial coefficient is basically telling me how many ways I can put j of the n objects into one "box", k of the objects into another, and the remaining in the last. But I'm summing 1 to j of them, and I'm not sure how to put it into combinatorical words.

Help?

Answer 1

HINT: You have $n$ balls and three boxes. $\binom{n}k$ is the number of ways to pick $k$ of the balls and put them in the first box. $2^{n-k}$ is the number of subsets of the remaining balls, so it can be thought of as the number of ways to pick a subset of them to put into the second box. Say you pick $j$ of them; what will you do with the remaining $n-k-j$ balls?

Answer 2

It is similar to the proof that $2^n = \sum_k \binom{n}{k}$.

Can you interpret the right hand side using three boxes?