basic combinatorics question

Question

Each person from a group of 3 people can choose his dish from a menu of 5 options. Knowing that each person eats only 1 dish what are the number of different orders the waiter can ask the chef?

Answer 1

This is a problem of combinations with repetitions. See for example the discussion on Wikipedia (which lacks a proof right now).

Answer 2

If we assume that the chef doesn't care which person ordered which dish, just how many of each dish to make, the problem is equivalent to placing 3 balls (each representing a dish the chef needs to make) in 5 urns (representing the 5 possible dishes). This type of balls/urns problem (or pieces of identical candy to children, donuts of different types, etc.) can be solved with a technique sometimes called "stars and bars": represent the balls by stars in a line:

* * *

Now, to divide these balls among 5 urns, add 4 bars, denoting the breaking points between different urns, e.g.:

* * * | | | |   all the balls in the first urn
* | | * * | |   1 balls in the first urn, 2 in the third urn, none in the rest

The number of possible ways to do this is the number of ways to rearrange the line of 3 *s and 4 |s, which is the number of ways to choose which 3 of the 7 symbols in the line should be *s, so ${7\choose 3}$. In general, for $k$ balls into $n$ urns, there are $k$ *s, $n-1$ |s, $k+n-1$ total symbols in the line, so ${k+n-1\choose k}$.

Answer 3

(5+2 choose 3)=(7 choose 3)=35 not (5 choose 3). The 35 different orders orders are {{1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 1, 4}, {1, 1, 5}, {1, 2, 2}, {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 3}, {1, 3, 4}, {1, 3, 5}, {1, 4, 4}, {1, 4, 5}, {1, 5, 5}, {2, 2, 2}, {2, 2, 3}, {2, 2, 4}, {2, 2, 5}, {2, 3, 3}, {2, 3, 4}, {2, 3, 5}, {2, 4, 4}, {2, 4, 5}, {2, 5, 5}, {3, 3, 3}, {3, 3, 4}, {3, 3, 5}, {3, 4, 4}, {3, 4, 5}, {3, 5, 5}, {4, 4, 4}, {4, 4, 5}, {4, 5, 5}, {5, 5, 5}}. The notation and formula were from http://www.oeis.org/A000292