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

-

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

-
A proof is here: en.wikipedia.org/wiki/Stars_and_bars_(probability) –  Douglas S. Stones Oct 20 '10 at 23:38

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}$.

-