Multinomial coefficient help please

[ipitydatfu]

multinomial Theorem help please

1. Prove this statement algebraically and by combinatorial argument
\left(\stackrel{n+1}{i,j,k}\right) = \left(\stackrel{n}{i-1,j,k}\right)+\left(\stackrel{n}{i,j-1,k}\right)+\left(\stackrel{n}{i,j,k-1}\right)


attempt

i tried expanding each side to see if i could relate one to another.

(n+1)!/(i! j! k!) = n!/(j!k!(i-1)!)+n!/(i!k!(j-1)!) + n!/(i!j!(k-1)!)

i can't seem to simplify either side to make one equate to the other side.

oh and can somebody explain how to prove something via combinatorial arguments. for some reason, my book just restates the equation in words, and goes, "hence this is proved" leaves me confused everytime

 

[Gib Z]

Ok well algebraically: you know the denominator you want to get on the RHS, so multiply each fraction by something to make it look like the LHS's denominator.

For combinatorial interpretation, think about what the multinomial coefficients represent. The actual expression from the trinomial case, \left(\stackrel{m}{a,b,c}\right) = \frac{m!}{a!b!c!} basically means "If I arrange 3 letters allowing repetitions into a line of total m letters, with "a" repetitions of one of the letters, "b" repetitions of another letter and "c" repetitions of the last letter, how many different ways can I arrange this string of letters? "

So the LHS says if i+j+k = n+1, and I have n+1 letters in a string with i,j and k repetitions, how many ways can I arrange it. The RHS on each term however only has n letters in the string - in other words it removed one. Can you continue?

 

[ipitydatfu]

so ok, i understood the algebraic portion.
ie for the fraction of (I-1)!

1/ (I-1)! = I/I! and so on for j, and k
using the LHS, I+J+K = n+1
once the denominators are the same, in the numerator of the RHS you get:
n!(n+1), which is the same as the (n+1)! on the LHS

combinatorially:
[STRIKE]so you're saying on the RHS, different ways to arrange a string of n letters of i,j,k,(minus 1 of their repititions), either way, subtracting 1 from i,j,k, would result in the same amount of arrangements

so:
i+j+(k-1)=i+(j-1)+k=(i-1)+j+k = n
i+j+k = n+1?[/STRIKE]

nvm i don't understand.

 

[Gib Z]

Well, I told you in words what the multinomial term can be thought of as. So express in words what the LHS says, and in words what the RHS says.

It might be easier to go form RHS to LHS; Remember LHS is arranging n+1 objects with i,j, and k repetitions. The RHS has only n terms to arrange. So it must be one term short on each and we have to add the term to get to n+1. What are the cases of the missing letter and what does that mean about the number of repeats for the each letter in the cases?