Results 1 to 11 of 11
Like Tree3Thanks
  • 1 Post By Plato
  • 1 Post By SlipEternal
  • 1 Post By Plato

Thread: Combinatorics problem

  1. #1
    Senior Member Vinod's Avatar
    Joined
    Sep 2011
    From
    Mumbai (Bombay),Maharashtra,India
    Posts
    341
    Thanks
    5

    Combinatorics problem

    Hello,

    A)In how many ways can I distribute 6 6 identical cookies and 6 6 identical candies to 4 4 children, if each child must receive at least 1 1 of each type of item?

    B)How many ways can 10 candy bars and 8 lollipops be given to five nameless, faceless, pitifully anonymous and altogether indistinct children so that every child gets at least one of each, but no child gets more than two lollipops?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,029
    Thanks
    2945
    Awards
    1

    Re: Combinatorics problem

    Quote Originally Posted by Vinod View Post
    A)In how many ways can I distribute 6 6 identical cookies and 6 6 identical candies to 4 4 children, if each child must receive at least 1 1 of each type of item?

    B)How many ways can 10 candy bars and 8 lollipops be given to five nameless, faceless, pitifully anonymous and altogether indistinct children so that every child gets at least one of each, but no child gets more than two lollipops?
    A) Think of this: give each child one cookie and one candy. Having done that, we now have two cookies & two candies to give to four kids.
    That can be done in $\dbinom{2+4-1}{2}\cdot \dbinom{2+4-1}{2}$ ways.

    Part B) is a "horse" of a different colour. This is known as an unordered partition.
    You have indistinguishable objects into indistinguishable cells. For that you need to study Stirling Numbers.

    As a rule, we are not prepared to give lessons on particular topics such as part B).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member Vinod's Avatar
    Joined
    Sep 2011
    From
    Mumbai (Bombay),Maharashtra,India
    Posts
    341
    Thanks
    5

    Re: Combinatorics problem

    Quote Originally Posted by Plato View Post
    A) Think of this: give each child one cookie and one candy. Having done that, we now have two cookies & two candies to give to four kids.
    That can be done in $\dbinom{2+4-1}{2}\cdot \dbinom{2+4-1}{2}$ ways.

    Part B) is a "horse" of a different colour. This is known as an unordered partition.
    You have indistinguishable objects into indistinguishable cells. For that you need to study Stirling Numbers.

    As a rule, we are not prepared to give lessons on particular topics such as part B).
    Hello,
    The formula used while answering A), seems to be ambiguous to me. Would you tell me what is the logic behind using that formula?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,029
    Thanks
    2945
    Awards
    1

    Re: Combinatorics problem

    Quote Originally Posted by Vinod View Post
    The formula used while answering A), seems to be ambiguous to me. Would you tell me what is the logic behind using that formula?
    This is a standard counting formula. It surely in your textbook/class-notes.
    The number of ways to place N identical objects into K different cells is:
    $\large\dbinom{N+K-1}{N}$

    Example: How many non-negative integer solutions are there to $x+y+z+w=20$
    Ans: $\dbinom{20+4-1}{20}$.
    Thanks from Vinod
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,681
    Thanks
    1491

    Re: Combinatorics problem

    For B) count it up. The lollipops are easiest to distribute. They are gonna be split 3 kids get two each while 2 kids get one each. Next split the candy bars.

    Let's consider the kids with 2 lollipops first followed by the kids with 1 lollipop each.
    6,1,1,1,1
    5,2,1,1,1
    5,1,1,2,1
    4,3,1,1,1
    4,2,2,1,1
    4,2,1,2,1
    4,1,1,3,1
    4,1,1,2,2
    3,3,2,1,1
    3,3,1,2,1
    3,2,2,2,1
    3,2,1,3,1
    3,2,1,2,2
    3,1,1,4,1
    3,1,1,3,2
    2,2,2,3,1
    2,2,2,2,2
    2,2,1,4,1
    2,2,1,3,2
    2,1,1,5,1
    2,1,1,4,2
    2,1,1,3,3
    1,1,1,6,1
    1,1,1,5,2
    1,1,1,4,3

    That's 25 ways to distribute the candy.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member Vinod's Avatar
    Joined
    Sep 2011
    From
    Mumbai (Bombay),Maharashtra,India
    Posts
    341
    Thanks
    5

    Re: Combinatorics problem

    Quote Originally Posted by SlipEternal View Post
    For B) count it up. The lollipops are easiest to distribute. They are gonna be split 3 kids get two each while 2 kids get one each. Next split the candy bars.

    Let's consider the kids with 2 lollipops first followed by the kids with 1 lollipop each.
    6,1,1,1,1
    5,2,1,1,1
    5,1,1,2,1
    4,3,1,1,1
    4,2,2,1,1
    4,2,1,2,1
    4,1,1,3,1
    4,1,1,2,2
    3,3,2,1,1
    3,3,1,2,1
    3,2,2,2,1
    3,2,1,3,1
    3,2,1,2,2
    3,1,1,4,1
    3,1,1,3,2
    2,2,2,3,1
    2,2,2,2,2
    2,2,1,4,1
    2,2,1,3,2
    2,1,1,5,1
    2,1,1,4,2
    2,1,1,3,3
    1,1,1,6,1
    1,1,1,5,2
    1,1,1,4,3

    That's 25 ways to distribute the candy.
    Hello,
    Is 5,1,2,1,1 possible?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,681
    Thanks
    1491

    Re: Combinatorics problem

    Quote Originally Posted by Vinod View Post
    Hello,
    Is 5,1,2,1,1 possible?
    5,1,2,1,1 represents the following candy distribution:
    5 candy bars + 2 lollipops
    1 candy bar + 2 lollipops
    2 candy bars + 2 lollipops
    1 candy bar + 1 lollipop
    1 candy bar + 1 lollipop

    How is that different from 5,2,1,1,1 which represents:
    5 candy bars + 2 lollipops
    2 candy bars + 2 lollipops
    1 candy bar + 2 lollipops
    1 candy bar + 1 lollipop
    1 candy bar + 1 lollipop
    ?

    The three children who received 2 lollipops are completely indistinguishable except by the number of candy bars they receive, so these two distributions represent the same case.
    Last edited by SlipEternal; Jun 25th 2018 at 04:54 AM.
    Thanks from Vinod
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,029
    Thanks
    2945
    Awards
    1

    Re: Combinatorics problem

    Quote Originally Posted by Vinod View Post
    B)How many ways can 10 candy bars and 8 lollipops be given to five nameless, faceless, pitifully anonymous and altogether indistinct children so that every child gets at least one of each, but no child gets more than two lollipops?
    I think that part b is being misread. It it is clear from the OP that the children are completely indistinguishable.
    There for $5,2,1,1,1$ is the same as $1,2,1,5,1$ for giving out the 10 candies.

    This calls for the number of partitions of the integer ten.
    If you follow that link, we see the there are seven partitions of ten of size five. That is the number of ways to put ten indistinguishable objects into five indistinguishable cells with no cell empty.

    Now to find the number of partitions of 8 of size five, we see the count is 3
    But we must include $3,2,1,1,1~\&~4,1,1,1,1$ why? That leaves only one way for the lollipops.

    So what is the answer to part (b) ?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,681
    Thanks
    1491

    Re: Combinatorics problem

    Quote Originally Posted by Plato View Post
    I think that part b is being misread. It it is clear from the OP that the children are completely indistinguishable.
    There for $5,2,1,1,1$ is the same as $1,2,1,5,1$ for giving out the 10 candies.

    This calls for the number of partitions of the integer ten.
    If you follow that link, we see the there are seven partitions of ten of size five. That is the number of ways to put ten indistinguishable objects into five indistinguishable cells with no cell empty.

    Now to find the number of partitions of 8 of size five, we see the count is 3
    But we must include $3,2,1,1,1~\&~4,1,1,1,1$ why? That leaves only one way for the lollipops.

    So what is the answer to part (b) ?
    Plato, I think you missed the part where I stated that the children who are receiving 2 lollipops are listed first followed by the children receiving 1 lollipop. Since a child must receive at least 1 and at most 2 lollipops, there is only 1 way to distribute the lollipops. Three children will receive 2 while 2 children will receive 1. This means that the order 5,2,1,1,1 is not the same as 1,2,1,5,1 because in the first you have a child receiving 5 candy bars and 2 lollipops while in the second order you have a child receiving 5 candy bars but only one lollipop. I appreciate you trying to correct me, but in this instance, I was correct already.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor

    Joined
    Aug 2006
    Posts
    22,029
    Thanks
    2945
    Awards
    1

    Re: Combinatorics problem

    Quote Originally Posted by SlipEternal View Post
    Plato, I think you missed the part where I stated that the children who are receiving 2 lollipops are listed first followed by the children receiving 1 lollipop. Since a child must receive at least 1 and at most 2 lollipops, there is only 1 way to distribute the lollipops. Three children will receive 2 while 2 children will receive 1. This means that the order 5,2,1,1,1 is not the same as 1,2,1,5,1 because in the first you have a child receiving 5 candy bars and 2 lollipops while in the second order you have a child receiving 5 candy bars but only one lollipop. I appreciate you trying to correct me, but in this instance, I was correct already.
    The OP clearly states that the children are indistinguishable.
    Thanks from SlipEternal
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,681
    Thanks
    1491

    Re: Combinatorics problem

    Quote Originally Posted by Plato View Post
    The OP clearly states that the children are indistinguishable.
    The children are indistinguishable, but the number of candies received are quite distinguishable. So, receiving 2 candies is different from receiving one candy. So, again, as I described, the case where a child receive 5 candy bars and 2 lollipops is different from a case where a child receives 5 candy bars and 1 lollipop. We are not distinguishing the children. We are distinguishing the NUMBER of candies being distributed. Do you see why I am saying these are different? Because if you still think they are the same, perhaps I am misreading the problem.

    Edit: I reread what I wrote and realized it sounded very patronizing. I did not mean it that way, so I reworded it. I apologize for how it came out originally.
    Last edited by SlipEternal; Jun 25th 2018 at 07:02 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Combinatorics problem
    Posted in the Algebra Forum
    Replies: 2
    Last Post: Feb 17th 2015, 09:08 AM
  2. problem in combinatorics
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 21st 2011, 08:23 AM
  3. Combinatorics Problem
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: May 1st 2010, 05:22 PM
  4. Combinatorics problem
    Posted in the Statistics Forum
    Replies: 6
    Last Post: Nov 12th 2009, 07:05 AM
  5. Help with combinatorics problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Sep 25th 2009, 08:21 AM

/mathhelpforum @mathhelpforum