I would recommend that you avoid too many nested conditions and loops. And is there a reason why you want your answer to involve a list comprehension? I like using them too, but beyond a point they become too long to, um... comprehend. Here's an alternative solution that uses fewer loops, avoids long list comprehensions and is easier to read -- to my eyes, at least. In [29]: from itertools import permutations, combinations_with_replacement In [30]: def all_valid_permutations(candies, members): ...: combos = combinations_with_replacement(range(1, candies), members) ...: valid_permutations = set() ...: for item in combos: ...: for perm in permutations(item): ...: if sum(perm) == candies and len(set(perm)) >= members-1: ...: valid_permutations.add(perm) ...: ...: return valid_permutations ...: In [31]: all_valid_permutations(6, 3) Out[31]: {(1, 1, 4), (1, 2, 3), (1, 3, 2), (1, 4, 1), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1), (4, 1, 1)}If you know your basic combinatorics you can guess what the imported functions do. (Or you can read the docs, if you prefer.) I can't guarantee performance, though, without fully knowing your use-case. This is just a quick solution, off the top of my head. I bet you can optimise this further. . In this my post, I will solve and explain you ONLY ONE problem of several posted. It is the problem n.2 about candies. In how many ways can five pieces of candy be divided between two children if each child receives at least one piece of candy? In this problem, candies are considered as NON-DISTINGUISHABLE - - - so the only difference between different cases is in the NUMBER of candies each child get. Without going into high and complicated Math, we can write the FULL LIST of all possible solutions/answers T A B L E 1st child 2nd child 1 4 2 3 3 2 4 1 It is the set of all possible different solutions. ANSWER. There are 4 (four) different solutions according to 4 different lines in the Table. Solved. //////////// Please DO NOT POST many (more than one) PROBLEMS PER POST. Post your problems SEPARATELY. It is the rule and the policy of this forum. Each your problem/question requires to give you a small lesson/lecture, and if some tutor will answer everything in one piece, you will get a mess. It is why the requirement "one problem per post" is established. Come again and enjoy my teaching ( ! ) \\\\\\\\\\\\ By the way, if the candies are considered as DISTINGUISHABLE in this problem, then the answer is 30: there are 30 different solutions in this case. 30 = 32 -2; 32 = 
Manager Joined: 16 Feb 2011 Posts: 156 Schools:ABCD
In how many ways can 5 different candiesbe distributed among [#permalink]
00:00
Difficulty:
Question Stats: Hide Show timer StatisticsIn how many ways can 5 different candies be distributed among four children? (Children could get 0 candies or more than one candy)(A) 4^5(B) 5^4(C) 5!(D) 4!(E) 4!*5!Method1 (Long method):N= the child doesn't get anything5-N-N-N : 4!/3! * 5C5 = 44-1-N-N : 4!/2! * 5C4 *1C1 = 5*12 = 603-2-N-N : 4!/2! * 5C3*2C2 = 12*10 =1203-1-1-N : 4!/2! * 5C3*2C2 = 12*10 = 1002-2-1-N : 4!/2! * 5C2*3C2*1c1 *(1/2) (1/2 because we are double counting 2-2) = 12 * 15 = 1802-1-1-1 : 4!/3! * 5C2*3C3 = 4*10=40If I add these numbers, it doesn't equal to 1024. What's my mistake? Thanks
Intern Joined: 14 Aug 2012 Posts: 7
Re: In how many ways can 5 different candiesbe distributed among [#permalink] there are total 5 candies. Lets say A,B,C,D and E.Candy A can be distributed among any 4 children. So there are 4 ways of distributing candy A.similarly candy B,C,D and E can be distributed in 4 ways.So total ways of distribution is4*4*4*4*4 = 4^5. A
Director Joined: 22 Mar 2011 Posts: 543 WE:Science (Education)
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
voodoochild wrote: In how many ways can 5 different candies be distributed among four children? (Children could get 0 candies or more than one candy)(A) 4^5(B) 5^4(C) 5!(D) 4!(E) 4!*5!Method1 (Long method):N= the child doesn't get anything5-N-N-N : 4!/3! * 5C5 = 44-1-N-N : 4!/2! * 5C4 *1C1 = 5*12 = 603-2-N-N : 4!/2! * 5C3*2C2 = 12*10 =1203-1-1-N : 4!/2! * 5C3*2C2 = 12*10 = 1002-2-1-N : 4!/2! * 5C2*3C2*1c1 *(1/2) (1/2 because we are double counting 2-2) = 12 * 15 = 1802-1-1-1 : 4!/3! * 5C2*3C3 = 4*10=40If I add these numbers, it doesn't equal to 1024. What's my mistake? Thanks 5-N-N-N : 4!/3! * 5C5 = 4 - OK 4-1-N-N : 4!/2! * 5C4 *1C1 = 5*12 = 60 - OK, divide by 2! because the two zero's (N) are indistinguishable3-2-N-N : 4!/2! * 5C3*2C2 = 12*10 =120 - OK3-1-1-N : 4!/2! * 5C3*2C2 = 12*10 = 100 - it should be 4! * 5C3 = 24*10 = 240, you should not divide by 2!, each ball is distinct2-2-1-N : 4!/2! * 5C2*3C2*1C1 *(1/2) (1/2 because we are double counting 2-2) = 12 * 15 = 180 - NO - it should be 4! * 5C2 * 3C2 * 1C1/2! = 360, doesn't matter which group of 2 you have chosen first, but later, when permuting them, it counts2-1-1-1 : 4!/3! * 5C2*3C3 = 4*10=40 - NO - it should be 4! * 5C2 = 240, all the balls are distinct, so you should not divide by 3!.The total is 4 + 60 + 120 + 240 + 360 + 240 = 1024.But why sweat all the way along???? _________________
PhD in Applied Mathematics
Manager Joined: 16 Feb 2011 Posts: 156 Schools:ABCD
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
EvaJager wrote: But why sweat all the way along???? 4 word answer : "No pain, no gain" --- something that my physical trainer taught me a few years ago.
Manager Joined: 12 Oct 2011 Posts: 100 GMAT 1: 700 Q48 V37 GMAT 2: 720 Q48 V40
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
EvaJager wrote: voodoochild wrote: In how many ways can 5 different candies be distributed among four children? (Children could get 0 candies or more than one candy)(A) 4^5(B) 5^4(C) 5!(D) 4!(E) 4!*5!Method1 (Long method):N= the child doesn't get anything5-N-N-N : 4!/3! * 5C5 = 44-1-N-N : 4!/2! * 5C4 *1C1 = 5*12 = 603-2-N-N : 4!/2! * 5C3*2C2 = 12*10 =1203-1-1-N : 4!/2! * 5C3*2C2 = 12*10 = 1002-2-1-N : 4!/2! * 5C2*3C2*1c1 *(1/2) (1/2 because we are double counting 2-2) = 12 * 15 = 1802-1-1-1 : 4!/3! * 5C2*3C3 = 4*10=40If I add these numbers, it doesn't equal to 1024. What's my mistake? Thanks 5-N-N-N : 4!/3! * 5C5 = 4 - OK 4-1-N-N : 4!/2! * 5C4 *1C1 = 5*12 = 60 - OK, divide by 2! because the two zero's (N) are indistinguishable3-2-N-N : 4!/2! * 5C3*2C2 = 12*10 =120 - OK3-1-1-N : 4!/2! * 5C3*2C2 = 12*10 = 100 - it should be 4! * 5C3 = 24*10 = 240, you should not divide by 2!, each ball is distinct2-2-1-N : 4!/2! * 5C2*3C2*1C1 *(1/2) (1/2 because we are double counting 2-2) = 12 * 15 = 180 - NO - it should be 4! * 5C2 * 3C2 * 1C1/2! = 360, doesn't matter which group of 2 you have chosen first, but later, when permuting them, it counts2-1-1-1 : 4!/3! * 5C2*3C3 = 4*10=40 - NO - it should be 4! * 5C2 = 240, all the balls are distinct, so you should not divide by 3!.The total is 4 + 60 + 120 + 240 + 360 + 240 = 1024.But why sweat all the way along???? Why do you have to divide by 2! on 2-2-1-N but don't have to divide by 2! on 3-1-1-N?
Director Joined: 22 Mar 2011 Posts: 543 WE:Science (Education)
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
BN1989 wrote: EvaJager wrote: voodoochild wrote: In how many ways can 5 different candies be distributed among four children? (Children could get 0 candies or more than one candy)(A) 4^5(B) 5^4(C) 5!(D) 4!(E) 4!*5!Method1 (Long method):N= the child doesn't get anything5-N-N-N : 4!/3! * 5C5 = 44-1-N-N : 4!/2! * 5C4 *1C1 = 5*12 = 603-2-N-N : 4!/2! * 5C3*2C2 = 12*10 =1203-1-1-N : 4!/2! * 5C3*2C2 = 12*10 = 1002-2-1-N : 4!/2! * 5C2*3C2*1c1 *(1/2) (1/2 because we are double counting 2-2) = 12 * 15 = 1802-1-1-1 : 4!/3! * 5C2*3C3 = 4*10=40If I add these numbers, it doesn't equal to 1024. What's my mistake? Thanks 5-N-N-N : 4!/3! * 5C5 = 4 - OK 4-1-N-N : 4!/2! * 5C4 *1C1 = 5*12 = 60 - OK, divide by 2! because the two zero's (N) are indistinguishable3-2-N-N : 4!/2! * 5C3*2C2 = 12*10 =120 - OK3-1-1-N : 4!/2! * 5C3*2C2 = 12*10 = 100 - it should be 4! * 5C3 = 24*10 = 240, you should not divide by 2!, each ball is distinct 2-2-1-N : 4!/2! * 5C2*3C2*1C1 *(1/2) (1/2 because we are double counting 2-2) = 12 * 15 = 180 - NO - it should be 4! * 5C2 * 3C2 * 1C1/2! = 360, doesn't matter which group of 2 you have chosen first, but later, when permuting them, it counts2-1-1-1 : 4!/3! * 5C2*3C3 = 4*10=40 - NO - it should be 4! * 5C2 = 240, all the balls are distinct, so you should not divide by 3!.The total is 4 + 60 + 120 + 240 + 360 + 240 = 1024. But why sweat all the way along???? Why do you have to divide by 2! on 2-2-1-N but don't have to divide by 2! on 3-1-1-N?In the case of 2-2-1-N we divide by 2! because we choose 2 groups of 2 one after the other and order when choosing them doesn't matter. Anyway, we permute them latter (see the factor of 4!).Similarly, in the case of 3-1-1-N we should divide by 2! if we choose one single ball after the other 4! * 5C3 * 2C1 * 1C1/2!.If it is clear that we split the two remaining balls after choosing 3, we don't need the 2C1 and 1C1 factors. That's why 4! * 5C3. _________________
PhD in Applied Mathematics
Manager Joined: 12 Oct 2011 Posts: 100 GMAT 1: 700 Q48 V37 GMAT 2: 720 Q48 V40
Re: In how many ways can 5 different candiesbe distributed among [#permalink] Thanks for your reply Eva, but I still haven’t fully understood it yet.Let’s use the 3-1-1-N example, let’s say the candies are named A, B, C, D and E:One possible outcome would be ABC-D-E-N, for this outcome there are 4! possible ways to distribute this outcome among the four people and 5C3 ways for the one person to get 3 candies so there are 240 possible arrangements of this kind. Now I don’t understand exactly how this would look like if we choose one candy after the other, so that this formula applies: 4! * 5C3 * 2C1 * 1C1/2! If you draw again ABC for the person who gets 3, you have D and E left for the next person so two choices and then you have again two choices about who out of the remaining two people gets the last candy?! So after ABC was picked you have 2C1*2!=4 options and you could permute this outcome in 4! ways, which obviously is wrong. How exactly does the process look like if I draw according to 4! * 5C3 * 2C1 * 1C1/2!?
Director Joined: 22 Mar 2011 Posts: 543 WE:Science (Education)
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
BN1989 wrote: Thanks for your reply Eva, but I still haven’t fully understood it yet.Let’s use the 3-1-1-N example, let’s say the candies are named A, B, C, D and E:One possible outcome would be ABC-D-E-N, for this outcome there are 4! possible ways to distribute this outcome among the four people and 5C3 ways for the one person to get 3 candies so there are 240 possible arrangements of this kind. Now I don’t understand exactly how this would look like if we choose one candy after the other, so that this formula applies: 4! * 5C3 * 2C1 * 1C1/2! If you draw again ABC for the person who gets 3, you have D and E left for the next person so two choices and then you have again two choices about who out of the remaining two people gets the last candy?! So after ABC was picked you have 2C1*2!=4 options and you could permute this outcome in 4! ways, which obviously is wrong. How exactly does the process look like if I draw according to 4! * 5C3 * 2C1 * 1C1/2!? How exactly does the process look like if I draw according to 4! * 5C3 * 2C1 * 1C1/2!? Think of carrying out the process in two steps:1) Divide the 5 candies into 3 groups - 3, 1, 1Decide on the 3 candies somebody will get them - 5C3 - for example A, B, C (but think of all the possibilities)Which one is the first 1 single candy - 2C1 - D or EWhich one is the second 1 single candy - 1C1 - E or DThis would give 5C3 * 2C1 * 1C1Divide by 2! because we are going to permute the groups of 3, 1, 1, 0, so we don't care about which single candy was chosen first. ABC, D, E is the same as ABC, E, D - what matters is that A, B, C are together, and D and E are single 2) After we have our groups of 3, 1, 1, 0 candies, we consider them as 4 distinct objects and just permute them - 4! - because we have 4 different kids. _________________
PhD in Applied Mathematics
Manager Joined: 12 Feb 2012 Posts: 109
Re: In how many ways can 5 different candiesbe distributed among [#permalink] I am getting 8!/(3!*5!)=56. I am using the stars bars method. (n+k-1)C(k-1). Why is this answer incorrect?
GMAT Expert Joined: 16 Oct 2010 Posts: 13270 Location: Pune, India
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
alphabeta1234 wrote: I am getting 8!/(3!*5!)=56. I am using the stars bars method. (n+k-1)C(k-1). Why is this answer incorrect? There are various methods of solving P&C questions and there are many formulas. You need to know the exact situation in which you can use a particular formula or better yet, you should understand the reason a particular method works in a particular situation.Stars bars method (or the formula (n+k-1)C(k-1)) is useful only when the objects to be distributed are identical. You split identical objects into different groups. You divide by 5! because the objects are identical. Here you can not use that method because the candies are different.Check out these posts on when to use which method:http://www.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html?/2011/12 ... 93-part-1/ http://www.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html?/2011/12 ... s-part-ii/ _________________
KarishmaOwner of Angles and Arguments Check out my Blog Posts here: Blog For Individual GMAT Study Modules, check Study Modules For Private Tutoring, check Private Tutoring
GMAT Expert Joined: 16 Oct 2010 Posts: 13270 Location: Pune, India
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
VeritasPrepKarishma wrote: There are various methods of solving P&C questions and there are many formulas. You need to know the exact situation in which you can use a particular formula or better yet, you should understand the reason a particular method works in a particular situation.Stars bars method (or the formula (n+k-1)C(k-1)) is useful only when the objects to be distributed are identical. You split identical objects into different groups. You divide by 5! because the objects are identical. Here you can not use that method because the candies are different.Check out these posts on when to use which method: http://www.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html?/2011/12 ... 93-part-1/ http://www.gmatclub.com/forum/veritas-prep-resource-links-no-longer-available-399979.html?/2011/12 ... s-part-ii/ alphabeta1234 wrote: Why is the same formula (n+r-1)C(r-1) used for number of ways of dividing n identical items among r persons whom can receive 0,1,2 or more items . Is the formula used even if each person can receive 2 or 3 or any item? Why isn't that being factored in to the formula?How many ways are there to distribute 10 mangoes among 4 kids if each kid must receive at least 1 mango?How many ways are there to distribute 10 mangoes among 4 kids if each kid must receive at least 2 mango?How many ways are there to distribute 10 mangoes among 4 kids if each kid must receive at least 3 mango? Are you saying this formula gives us the same answer for all these questions? (10+4-1)C(4-1)? Certainly not. You will not have the same answer in every case. You can use the same formula but the value of n will vary in each case.Say if every kid must receive at least one mango, you take any 4 mangoes from the bunch of 10 (they are identical) and give one to each of the 4 kids. You cannot do this in more than 1 way because all the mangoes are the same and all the kids are receiving exactly one mango.Next, you are left with 6 mangoes and 4 kids and you need to distribute these 6 among the kids such that a kid may get no mango and another may get all etc. (You can do this because all the kids have already got a mango each and hence our condition is already satisfied.) This boils down to our previous question except that the value of n = 6 now, not n = 10.Now you use the formula as (6 + 4 - 1)C(4 - 1) = 9!/6!*3!You can do the same thing for at least 2 mangoes too. _________________
KarishmaOwner of Angles and Arguments Check out my Blog Posts here: Blog For Individual GMAT Study Modules, check Study Modules For Private Tutoring, check Private Tutoring
Intern Joined: 26 Jul 2015 Posts: 10
In how many ways can 5 different candiesbe distributed among [#permalink] Why do we ignore the case in which no candy is given to any child? It is literally in the question statement that the children could get zero candies: Quote: In how many ways can 5 different candies be distributed among four children? (Children could get 0 candies or more than one candy) Admittedly, I'm not a native English speaker but to me it's clear that I do not have to give a candy to any child. I can keep all candies to myself. Nor does the question state that all five candies must be given out to children. I could give out 0, 1, 2, 3, 4, or all five.So, using the awesome approach posted by shrikar23, we would get 5^5 because there are 5 ways of giving out each distinct candy: give it to no child, or to child 1, or to child 2 and so forth.
GMAT Expert Joined: 16 Oct 2010 Posts: 13270 Location: Pune, India
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
jhabib wrote: Why do we ignore the case in which no candy is given to any child? It is literally in the question statement that the children could get zero candies: Quote: In how many ways can 5 different candies be distributed among four children? (Children could get 0 candies or more than one candy) Admittedly, I'm not a native English speaker but to me it's clear that I do not have to give a candy to any child. I can keep all candies to myself. Nor does the question state that all five candies must be given out to children. I could give out 0, 1, 2, 3, 4, or all five.So, using the awesome approach posted by shrikar23, we would get 5^5 because there are 5 ways of giving out each distinct candy: give it to no child, or to child 1, or to child 2 and so forth. The question states that you need to "distribute 5 candies". So all 5 candies must be given out. It is possible that one or more children may not get any candy and one or more may get more than one candies but all 5 have to be distributed. _________________
KarishmaOwner of Angles and Arguments Check out my Blog Posts here: Blog For Individual GMAT Study Modules, check Study Modules For Private Tutoring, check Private Tutoring
Manager Joined: 05 Oct 2017 Posts: 54 GMAT 1: 560 Q44 V23
Re: In how many ways can 5 different candiesbe distributed among [#permalink]
Quote: In how many ways can 5 different candies be distributed among four children? (Children could get 0 candies or more than one candy) what will be answer if candies are similar? _________________
Manager Joined: 15 Feb 2021 Posts: 99
Re: In how many ways can 5 different candiesbe distributed among [#permalink] I think there are some mistakes in the previous explications.There are two ways of solving it:- Fastest wayInstead of thinking you have to distribute candies among children you can think in distribute children among candies.So you have 5 candies and 4 children. And you can "repeat" children. So it is a permutation with repetition of 4 children in 5 ways (candies): 4^5 = 1024- Slowest way5-N-N-N : 4!/3! * 5C5 = 44-1-N-N : 4!/2! * 5C4*1C1 = 12*5*1 = 603-2-N-N : 4!/2! * 5C3*2C2 = 12*10*1 = 1203-1-1-N : 4!/2! * 5C3*2C1*1C1 = 12*10*2*1 = 2402-2-1-N : 4!/2! * 5C2*3C2*1C1 = 12*10*3*1 = 3602-1-1-1 : 4!/3! * 5C2*3C1*2C1*1C1 = 4*10*3*2*1 = 2404+60+120+240+360+240 = 1024 = 4^5Explication:For example, in the 3-1-1-N row, 4!/2! are the ways you can arrange 3-1-1-N (1-1-3-N, 1-1-N-3, 1-3-1-N, 1-3-N-1, 1-N-1-3, 1-N-3-1, 3-1-1-N, 3-1-N-1, 3-N-1-1, N-1-1-3, N-1-3-1, N-3-1-1): total 12 ways. So you have decided the number of candies that each boy is going to receive.But candies are different (as the statement says) so we have to choose wich candies you give to each child (according with the number chosen before). In this case order does not mind because if a child receives gummi bears, cotton candy and M&M is the same as he receives M&M, cotton candy and gummi bears. So we use combinations: 5C3*2C1*1C1. First we choose which candies will be for the child who receives 3 (5C3). After that we have 2 remaining candies. We can choose which candy to give to one of the children who receives one (2C1). And the remaining candy is given to the other child (1C1).
VP Joined: 10 Jul 2019 Posts: 1426
In how many ways can 5 different candiesbe distributed among [#permalink] Agreed. Great analysis. andreagonzalez2kI work it out a bit backwards (I suppose) but get the same result going through the slow way. Ive always followed this way to keep the calculations and reasoning straight in my head (although I think it adds an extra step):(1st) for each case I divide the different items into identical “stacks”(2nd)then I account for any over counting if we have “stacks” of the same size(3rd)then I arrange each of the “identical” stacks and shuffle them among the 4 different children, treating any child who gets 0 more than once as “identical elements”Case 1: 5-0-0-0(1st) no. of ways to choose candies5 c 5 = 1(2nd) we can arrange this 1 stack among the 4 children in:4!/3! Ways (we need to remove the arrangements in which the children who receive 0 are over counted in 4!)(5 c 5) * (4!/3!) = 1 * 4 = 4Case 2: 4-1-0-0(1st) no of ways to break chocolate into “identical stacks”(5 c 4) * (4 c 1) = 5And(2nd) for each of the ways to break down the Items into non-distinct stacks, we can shuffle the stacks among the 4 children:4!/2! = 125 * 12 = 60Case 3: 3-2-0-0(1st) choose and select the candies to break into identical “stacks”(5 c 3) * (2 c 2) = 10And(2nd) for each of the 10 ways to break down into non-distinct stacks, we can shuffle around and arrange the identical stacks in:4!/2! = 4 * 3 = 1210 * 12 = 120Case 4: 3-1-1-0(1st) here is where the way I do it may differ a little (though we end up with the same calculation): 1st, we choose the ways to break down the different chocolates into stacks:(5 c 3) * (2 c 1) * (1 c 1) But, for the stacks that are of the SAME SIZE (1 and 1) we will be over counting each one through the selection method - right now, we are ignoring the ordering. So multiply the above result by (1 / 2!)(5! / 3! 1! 1!) * (1 / 2!) = 10 waysAnd(2nd) for each of these 10 ways to break down the different chocolates into non-distinct stacks, we can then shuffle the stacks among the 4 children in;4! = 24 ways 10 * 24 = 240Case 5: 2-2-1-0(1st) breaking down into identical stacks, but again we have two stacks of the same size (and will be over counting)(5 c 2) * (3 c 2) * (1 c 1) * (1 / 2!) = 15 ways And(2nd) for each of the 15 ways to beak the Choc down into non-distinct stacks, these stacks can be shuffled around the 4 children in:4! = 24 ways15 * 24 = 360Case 6: 2-1-1-1(1st) (5 c 2) (3 c 1) (2 c 1) (1 c 1) * (1 / 3!) = 10And(2nd) 4! = 2410 * 24 = 240Adding up the cases:4 + 60 + 120 + 240 + 360 + 240 =1024 Posted from my mobile device
Manager Joined: 15 Feb 2021 Posts: 99
Re: In how many ways can 5 different candiesbe distributed among [#permalink] The problem of choosing the slowest way is not to waste too much time...
Re: In how many ways can 5 different candiesbe distributed among [#permalink] 11 Jul 2021, 10:33 |
How many ways can five pieces of candy be divided between two children if each child receives at least one piece of candy?
Related Posts
Copyright © 2024 SignalDuo Inc.
