1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Multinomial coefficient help please

  1. Nov 3, 2009 #1
    multinomial Theorem help please

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


    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 cant 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
     
    Last edited: Nov 3, 2009
  2. jcsd
  3. Nov 4, 2009 #2

    Gib Z

    User Avatar
    Homework Helper

    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, [tex]\left(\stackrel{m}{a,b,c}\right) = \frac{m!}{a!b!c!}[/tex] 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?
     
  4. Nov 4, 2009 #3
    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 dont understand.
     
    Last edited: Nov 4, 2009
  5. Nov 5, 2009 #4

    Gib Z

    User Avatar
    Homework Helper

    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Multinomial coefficient help please
  1. Multinomial Theorem (Replies: 2)

  2. Multinomial Expansion (Replies: 5)

Loading...