Date: 10/11/2002 at 00:10:53 From: Tim Darling Subject: Combinations and permutations A number of my friends and I have already wrestled with this one, and have had no success: There are 8 identical apples, and they are to be given out to 4 children. How many different ways of distributing the apples are there if each child must receive at least one apple? Please help if you can. It would be greatly appreciated.
Date: 10/11/2002 at 06:08:10 From: Doctor Anthony Subject: Re: Combinations and permutations Place the 8 apples in a row with gaps between then. See diagram below. * * | * | * * * * | * To divide the apples into 4 groups we must choose 3 separators '|' to place in the gaps. There are 7 gaps and we must choose 3 from amongst the 7. This can be done in C(7,3) = 35 ways - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Date: 10/11/2002 at 09:12:36 From: Doctor Mitteldorf Subject: Re: Combinations and permutations Doctor Anthony has shown you an elegant way to do the problem abstractly. The advantage of this approach is that you can see how to extend it to other, similar problems: for example, n identical apples to be distributed among m children. The trick, in case Doctor Anthony was too concise in his explanation, is this: Imagine the n apples laid out on a grocery checkout counter with n-1 gaps between them. First, put the m children in a particular order in front of the checkout. Then you can put m-1 dividers in to separate which child gets which apples. Since there are n-1 gaps, with m-1 dividers to be inserted, the answer is the same as a combinatorial problem: How many ways can you choose m-1 things out of a list of n-1 in all? This is the number from Pascal's Triangle, often denoted by C(n-1,m-1), or "n-1 choose m-1." Notice that putting two dividers into one slot would correspond to a child getting no apples, so we don't want to allow that in this case. For the same reason, you can't put a divider at the extreme left end or the extreme right end. (The children are "distinguishable" but the apples are "indistinguishible," meaning we care which child gets how many apples but if Amy gets two apples, we don't care which particular two are hers.) This is a simple case of a "partition problem," and there are more complicated variations if the apples are regarded as distinguishable. Doctor Anthony has written about this context in several contexts: Stirling Numbers http://mathforum.org/library/drmath/view/51550.html Distributing Objects http://mathforum.org/library/drmath/view/56233.html Partitioning Elements http://mathforum.org/library/drmath/view/52275.html Finally, I want to suggest that 35 isn't too many to count. You could just literally make a list. I think this is useful - in fact all combinatorial formulas begin with counting. As you invent symbols for the objects you want to count, you just naturally begin to categorize and group them. Then you see patterns in how many symbols there are in each group, and you begin to move toward a general formula. In this case, you might say: 8 apples could be distributed 5-1-1-1, or 1-5-1-1, or 1-1-5-1, or 1-1-1-5. But all these are the same, except for ordering. It would be a good shortcut to just write 5-1-1-1 and note that there are 4 different positions to put the 5, so we count 4 partitions of this type. Similarly, 4-2-1-1 has 12 orderings, C(4,2), since there are 4 possibilities for which child gets the 4 times 3 possibilities for which other child gets the 2. Continuing: 3-3-1-1 has 6 orderings, and 3-2-2-1 has 12 orderings, while 2-2-2-2 has just 1. Add them all up: 5111 4 4211 12 3311 6 3221 12 2222 1 ------ 35 - Doctor Mitteldorf, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2015 The Math Forum