Number of multisets

Question

There's a question that asks how many $4$-element multisets are there whose elements are taken from the set $\{a, b, c\}$.

I thought that there were $3$ options for each element, but they listed all the options and there are $15$. What am I thinking wrong?

Thanks in advance.

Answer 1

Hint: Call $x_a,x_b,x_c$ the number of times you will have $a,b,c$ in the multiset, then you know that $x_a+x_b+x_c=4 $ and $x_a,x_b,x_c\geq 0.$ Probably you are not taking into account that at the end you need to have exactly $4$ elements.

Answer 2

The issue is that there are $3^4$ ordered multisets, but you want the number of unordered multisets. So $a,a,b,c$ and $a,b,c,a$ are the same multiset, but your method counts them both separately in the $3^4$.

The easiest way to do this is sometimes called "stars and bars". Imagine that you list the elements of your multiset in alphabetical order, e.g. $aabc$. Now place a bar between the $a$s and $b$s (if there are no $a$s, this just goes at the start), and another between $b$s and $c$s, e.g. $aa|b|c$. Now if you were to replace all the letters by stars, e.g. $**|*|*$, you would still be able to work out the multiset: there are two stars before the first bar, so two $a$s, etc.

Thus there is a one-toone correspondence between multisets and sequences of $4$ stars and $2$ bars. But the number of these sequences is the number of ways to choose $2$ places for the bars out of $4+2$, i.e. $\binom 62=15$.