I'm playing a peculiar lottery. We pick $5$ numbers from $\{1, ..., 9\}$, order doesn't matter, repetition is allowed.
The question here is, how many $5$ element multisets can I create from $\{1, ..., 9\}$. To solve the problem and get an intuition, I made use of a mental model called "stars and bars".
Imagine 5 buckets. Now we sort $9$ items into these $5$ buckets. We can represent such an arrangement like so:
**|****|***||
The above could be represented as a $5$-tuple like so $(2, 4, 3, 0, 0)$, meaning we put $2$ items in the first bucket, $4$ items in the second etc.
We have $9$ stars to represent the items, and $5-1=4$ bars to segregate the buckets.
In general we have $9 + 5 - 1=13$ slots, onto which we distribute $9$ stars and $4$ bars as separators.
For the $9$ stars, there are $13! / 5!$ ways to arrange them, and since order doesn't matter among the stars, we divide by another $9!$ to find the count of all possible stars/bars arrangements:
$$\frac{13!}{9!5!} = \binom{9 + 5 - 1}{5}$$
But what I don't understand is, the above counts the ways how to create $5$-tuples like $(a_1, a_2, a_3, a_4, a_5)$ etc. But how does this relate to $5$-element multisets chosen from $\{1, ..., 9\}$ ?
In other words, for a given $5$-tuple, what's the bijection onto multisets from $\{1, ..., 9\}$?
My conjecture:
- In total there are $\binom{9}{5}$ ways to find a set of $5$ unique numbers $A=\{n_1, n_2, n_3, n_4, n_5\}$.
- Now I want to create multisets of $5$ numbers from $A$. Each number $n_i$ can appear at most $5$ times in a multiset, and at least $0$ times. That is what the $5$-tuple found by stars and bars represents, say $(a_1, a_2, a_3, a_4, a_5)$. If $a_i=1$, let $n_1$ appear 1 time, etc.
I'm not sure if the above makes sense, I have my doubts. Hence my question, how to think about relating the tuples found via the stars/bars method back to the original question about multisets.
You can use stars and bars, but the buckets should represent the numbers $1$ through $9$, and you should have $5$ balls, one for each pot. For instance, the arrangement
$$\mid\;\mid**\mid\;\mid\;\mid*\mid\;\mid**\;\mid$$
corresponds to the multiset $\lbrace\!\lbrace 3,3,6,8,8\rbrace\!\rbrace$. Now you have any string of $5$ stars and $8$ bars, so there are altogether
$$\binom{5+8}5=\binom{13}8=\binom{13}5=1287$$
multisets of $5$ elements from the set $\{1,2,3,4,5,6,7,8,9\}$.