Results 1 to 5 of 5

Math Help - Combinatorics question

  1. #1
    Junior Member
    Joined
    Nov 2010
    Posts
    41

    Combinatorics question

    a) What is the number of sequences of length 20 of 1, -1 so that the total sum of the numbers is 0?
    The answer is 20 choose 10 right?

    This is what I'm stuck on:
    b) How many of the sequences in part a) have a positive sum for the first k numbers and a negative sum for the first m numbers? (where 1≤k≤m≤20)

    Thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Unknown008's Avatar
    Joined
    May 2010
    From
    Mauritius
    Posts
    1,260
    a) Nope.

    To get 0, you need to have exactly 10 of -1 and 10 of 1.

    Now the number of sequences is \dfrac{20!}{10! \times 10!}

    20! is 'shuffling' all the 20 terms
    10! is dividing by the number of ways -1 can be arranged because there are 10 similar -1
    The other 10! is for 1.

    EDIT: Cross that out, I messed up P and C... again -.-

    b) I don't know the shortcut (though I'd like to learn about it) but I could do by the long way.

    For the first k numbers, the sum is positive when you have:
    k = 1, first term 1
    k = 2, first terms 1 1
    k = 3, first terms 1 1 1, or 1 1 -1
    k = 4, first terms 1 1 1 1, or 1 1 1 -1
    k = 5, first terms 1 1 1 1 1, or 1 1 1 1 -1, or 1 1 1 -1 -1
    .
    .
    .
    k = 10, first terms 10(1), or 9(1)1(-1), or 8(1)2(-1), or 7(1)3(-1), or 6(1)4(-1)

    Then, you multiply by 2 due to the symmetry for the last term to be negative.

    When k = 1, you have \dfrac{19!}{10! \times 9!}

    When k = 10, you have \dfrac{10! \times 10!}{10! \times 10!} + \dfrac{10! \times 10!}{9! \times 9!} + \dfrac{10! \times 10!}{8!\times 2!\times 2!\times 8!} + \dfrac{10! \times 10!}{7!\times 3!\times 3!\times 7!} + \dfrac{10! \times 10!}{6!\times 4!\times 4!\times 6!}

    Okay, maybe a summation formula would simplify that calculation...
    Last edited by Unknown008; February 24th 2011 at 09:17 AM. Reason: LaTeX error corrected
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Unknown008 View Post
    a) Nope.
    To get 0, you need to have exactly 10 of -1 and 10 of 1.
    Now the number of sequences is \dfrac{20!}{10! \times 10!}
    It is worth pointing out that:
    \dbinom{20}{10}=\dfrac{20!}{10! \times 10!} that is a combination of twenty choosing ten.

    I don't understand what part (b) means.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Unknown008's Avatar
    Joined
    May 2010
    From
    Mauritius
    Posts
    1,260
    But isn't

    \displaystyle \binom{20}{10} = \dfrac{20!}{10!}

    Now, I'm very confused >.<

    EDIT: Sorry, that's 20P10. I'll be correcting my above mistake...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by Unknown008 View Post
    But isn't
    \displaystyle \binom{20}{10} = \dfrac{20!}{10!}
    \displaystyle \binom{N}{k} = \dfrac{N!}{k!(N-k)!}
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: May 2nd 2011, 03:30 AM
  2. combinatorics question
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: April 10th 2011, 10:37 AM
  3. Combinatorics question
    Posted in the Statistics Forum
    Replies: 2
    Last Post: December 16th 2008, 10:12 AM
  4. Combinatorics Question
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 10th 2008, 10:21 AM
  5. Combinatorics question
    Posted in the Advanced Math Topics Forum
    Replies: 5
    Last Post: December 8th 2007, 02:12 PM

Search Tags


/mathhelpforum @mathhelpforum