Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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

share|improve this answer
2  
A proof is here: en.wikipedia.org/wiki/Stars_and_bars_(probability) –  Douglas S. Stones Oct 20 '10 at 23:38

(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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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