1
$\begingroup$

This question is from Kenneth P. Bogart's book "Combinatorics through guided discovery" which can be freely downloaded at

https://math.dartmouth.edu/news-resources/electronic/kpbogart/FDL-bogart/kpbogart-FDL.tar.gz

The question is

  1. Assuming $k ≤ n$, in how many ways can we pass out $k$ distinct pieces of fruit to $n$ children if each child may get at most one ?

What is the number if $k > n ?$ (I know the answer to this one!)

Assume for both questions that we pass out all the fruit.

Solution: (quoted from the book)

There are $n$ choices for the child to whom the first piece of fruit goes, then n−1 choices for the second, and, in general, $n−i+1$ choices for the $ith$ piece of fruit.

By the general product principle, this gives us

$$\prod_{i=1}^{k} n − i + 1$$

ways to pass out the fruit.

The number of ways to pass out the fruit is zero if k > n, because the problem says each child has to get at most one piece of fruit, and that all the fruit must be passed out. This is impossible if k > n, so there are zero ways to pass out the fruit.

end quote from the book

Using 3 children, C1, C2 and C3 and 2 distinct fruits F1 and F2. Counting the ways were one child gets no fruit (indicated by a lone slash), I obtain the following

C1/F1   C1/F1   C1/F2   C1/F2   C1/     C1/
C2/F2   C2/     C2/F1   C2/     C2/F1   C2/F2
C3/     C3/F2   C3/     C3/F1   C3/F2   C3/F1

resulting in 18 ways. Leaving out the combinations where a child gets no fruit (that would be the $n - 1$ referred to in the solution), I obtain

C1/F1   C1/F1   C1/F2   C1/F2
C2/F2   C3/F2   C2/F1   C3/F1

thereby resulting in 8 ways.

The resulting product in the book when $n = 3$ and $k = 2$ gives $(3 - 1 + 1) \cdot (3 - 2 + 1)$ which yields 6. The least number of ways I see in that case is 8, not 6.

What am I getting wrong ?

Thank you,

John.

$\endgroup$
2
$\begingroup$

Your "$18$" ways, are really just $6$ ways! One "way" is not a single $<$child-fruit$>$ pair, but a triple of pairs $<$child,fruit$>$ (or $<$child,no-fruit$>$); i.e. one entire "column" in your post.

$\endgroup$
  • $\begingroup$ Thank you, now I see my error. $\endgroup$ – MathAddict Feb 28 '17 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.