Results 1 to 6 of 6

Math Help - Combinatorial Math Problem

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    12

    Combinatorial Math Problem

    I've forgotten the methodology for deducing the number of ways to select N groups from M objects. For example, if I had 11 flags, how many ways would there be to put the 11 flags in 5 piles?

    The real question I'm working on is:

    "How many integer solutions are there to the equation x1 + x2 + x3 + x4 + x5 = 21, if xi >= 2 for i = 1, 2, 3, 4, 5."

    I was going to try and think about it as having 5 groups of at least 2 (since each xi much be at least 2) and then distribute the remaining 11 groups of 1 between the 5 groups.
    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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,652
    Thanks
    1600
    Awards
    1
    I can help you with the second one.
    The number of non-negative integer solutions to x_1  + x_2  + x_3  + x_4  + x_5  = 21 is the standard {{21+5-1} \choose {21}}.
    But if you want to restrict x_i  \ge 2 the answer is {{11+5-1} \choose {11}}.
    Note the change to 11. The mind trick here is to think of putting two ones into each variable.
    That uses ten ones leaving eleven ones to distribute.

    The first one is really ambiguous. Not sure about piles. Can you have an empty pile?
    Are the piles distinguishable other that by number contained?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    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
    Quote Originally Posted by Moo View Post
    To complete on that... If you want x_i \ge 2, substitute : y_i=x_i-2 \quad (\implies x_i=y_i+2)

    Thus y_i \ge 0 and 21=x_1+x_2+x_3+x_4+x_5=y_1+y_2+y_3+y_4+y_5+5 \cdot 2 \implies y_1+y_2+y_3+y_4+y_5=11

    Hence the formula Plato gave =)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jul 2008
    Posts
    12
    Quote Originally Posted by Plato View Post
    I can help you with the second one.
    The number of non-negative integer solutions to x_1  + x_2  + x_3  + x_4  + x_5  = 21 is the standard {{21+5-1} \choose {21}}.
    But if you want to restrict x_i  \ge 2 the answer is {{11+5-1} \choose {11}}.
    Note the change to 11. The mind trick here is to think of putting two ones into each variable.
    That uses ten ones leaving eleven ones to distribute.
    So I'm trying to rationalize this here, and I'm having some difficulty.

    In the first situation, I evaluate:

    (21+5+1)! / 21!4! = 12650

    This seems plausible, but it seems to me that:

    4+4+8+2+3 = 21

    is counted twice, once for the arrangement you see there and once for:

    4+4+8+3+2 = 21

    I tried dividing by 5!, but 12650 is not evenly divisible by 5!, which seemed odd to me at first.

    But then I thought, because of the nature of what we're doing, taking a set of "a"s and putting "b"s in-place to separate groups, the two different "orderings" of the identical "4"s isn't double-counted, but "3" and "2" in reversed order is counted twice.

    Help?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,652
    Thanks
    1600
    Awards
    1
    Quote Originally Posted by InfinitePartsInHarmony View Post
    This seems plausible, but it seems to me that: 4+4+8+2+3 = 21
    is counted twice, once for the arrangement you see there and once for:
    4+4+8+3+2 = 21
    Those two solutions are different if x_4 \ne x_5.
    What is the exact wording of the question?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 16th 2011, 03:39 PM
  2. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 4th 2011, 09:05 AM
  3. combinatorial problem??
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 23rd 2009, 10:29 PM
  4. Combinatorial problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 13th 2008, 06:22 PM
  5. Replies: 4
    Last Post: January 26th 2008, 11:10 PM

Search Tags


/mathhelpforum @mathhelpforum