Distributing Apples

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/