Associated Topics || Dr. Math Home || Search Dr. Math

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

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?

```

```
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.

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.

5111         4
4211        12
3311         6
3221        12
2222         1
------
35

- Doctor Mitteldorf, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search