# Choosing k Multisets from [n]

We are to play a lottery game where five numbers are drawn out of [90], but the numbers drawn are put back into the basket right after being selected. To win the jackpot, one must have played the same multiset of numbers as the one drawn (regardless of the order in which the numbers were drawn). How many lottery tickets do we have to buy to make sure that we win the jackpot?

It has been explained that the binomial coefficient (94,5) solves the problem. This is done by creating a bijection. However, I don't see why it is 94. I find myself trying to deconstruct it as a pigeonhole problem and failing. Does anyone have an explanation as to why this is the correct answer?

-

The number of multisets of numbers drawn is equivalent to the number of nonnegative integer solutions to the following equation, where $a_i$ corresponds to the number of balls with number $i$ that are chosen.

$$a_1+a_2+a_3+...+a_{90}=5$$

For example, $a_1=1, a_{53}=2, a_{59}=1, a_{89}=1$ corresponds to the multiset ${1, 53, 53, 59, 89}$.

But how do we find the number of nonnegative integer solutions to the above sum? Well, we can use the ball-and-star model, where we have 5 (identical) balls and 89 (identical) stars.

We establish a bijection between each ordering of the balls and stars and a nonegative integer solution to the above sum as follows: the number of balls to the left of the first star corresponds to $a_1$, that between the first and second star corresponds to $a_2$, between the second and third star corresponds to $a_3$, and so on until the number of balls after the last star corresponds to the value of $a_{90}$.

Given that number of balls and stars, we know that there are exactly $94 \choose 5$ ways to order the balls and stars, which corresponds to the number of multisets drawn.

-
Do you mean 5 identical stars and 90-1 bars Vincent? Is this to say that there are 5 indistinct objects being placed in 90 distinct slots? Thanks for your response! – 114 Mar 1 '13 at 16:48
yep, if you're thinking of it as stars and bars it works too - 5 indistinct objects being placed into 90 distinct slots. – Vincent Tjeng Mar 1 '13 at 16:54
Thanks again, I need to get better at interpreting these sorts of problems! – 114 Mar 1 '13 at 17:11
don't worry - it comes with practice! the key is normally to identify whether the objects are distinct or indistinct, and whether the slots are distinct or indistinct; once you've done so, you will be able to use a standard method to deal with each of the four possibilities. – Vincent Tjeng Mar 1 '13 at 17:27