Results 1 to 2 of 2

Math Help - combinatorial proof

  1. #1
    Member
    Joined
    Apr 2008
    Posts
    85

    combinatorial proof

    i hate these proofs i never understand what they mean i cant seem to get me head around them all tips appreciated.

    show that the number of integer sequences ( e_{1},e_{2},...,e_{n}) such that    0\leq e_{i} , i=1,2,..,n and  e_{1} +e_{2} +...+e_{n}=k is equal to

    ( n + k - 1 ) (brackets are meant to be over k aswel...
    k

    thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Hello,

    Quote Originally Posted by skystar View Post
    i hate these proofs i never understand what they mean i cant seem to get me head around them all tips appreciated.

    show that the number of integer sequences ( e_{1},e_{2},...,e_{n}) such that    0\leq e_{i} , i=1,2,..,n and  e_{1} +e_{2} +...+e_{n}=k is equal to

    ( n + k - 1 ) (brackets are meant to be over k aswel...
    k

    thanks.
    I'll show you the way one of my teacher taught us


    We'll keep your hypothesis.

    Make a word this way :

    \underbrace{a\dots a}_{e_1 \text{ times}}b\underbrace{a\dots a}_{e_2 \text{ times}}b \dots b\underbrace{a\dots a}_{e_n \text{ times}}

    Do you agree that there are e_1+e_2+\dots+e_n=k letters a ?
    Plus, there are n-1 letters b (I'll let you do the counting).
    Therefore, this word has k+(n-1) letters.

    So we're looking for all words of k+(n-1) letters and containing k letters a and n-1 letters b.

    This is the part you have to understand : it's equivalent to finding the possible places where b can be.

    So this is the combinations of (p-1) among k+(n-1)..

    If I have time, I'll try to post an example...
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 10th 2011, 01:42 PM
  2. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 21st 2010, 02:47 AM
  3. Combinatorial Proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 4th 2010, 04:12 PM
  4. Combinatorial proof help
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: September 30th 2009, 05:43 PM
  5. Combinatorial proof?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 24th 2008, 06:20 PM

Search Tags


/mathhelpforum @mathhelpforum