# 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?

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 ﬁrst 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.

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.