Multinomial coefficient or stars and bars for $k$ sided dice rolls?

Question

The wikipedia page for the multinomial distribution says it can represent the probability of counts for each side of a $k$-sided dice rolled $n$ times. But this StackExchange answer says the same quantity is counted using stars and bars. Which is right, or how are the quantities being counted differently in a way I'm not seeing?

To me it seems that the counts for each side of a $k$ sided dice rolled $n$ times should be done using stars and bars as per the logic of the SE answer, and not the multinomial coefficient.

The application of the multinomial coefficient $\frac{n}{x_1!x_2!...x_k!}$ that I'm aware of is counting counting the number of strings with repeated letters, e.g. the number of rearrangements of MISSISSIPPI is $\frac{11!}{1!4!4!2!}$.

If think of the $i$th letter as indicating the outcome of the $i$th trial, with $k$ possible letters for $k$ different possible outcomes, then these strings represent sequences of outcomes of each trial. The multinomial coefficient counts these sequences, but shouldn't we be counting the number of occurrences of each outcome while ignoring the order? For example, the multinomial coefficient distinguishes between the sequences $abca$ and $aabc$. To be invariant to the order, we need to use stars and bars?

Answer 1

Consider a very simple example, $k = n = 2.$ This is equivalent to tossing a coin twice, where we consider a coin to be a "two-sided" die with a $1$ on the tails side and $2$ on the heads side.

According to the stars-and-bars interpretation, there are only three outcomes to be counted: two tails, two heads, or one tail and one head.

According to the multinomial interpretation, there are four outcomes to be counted:

• Tails on both tosses.
• Tails on the first toss, heads on the second toss.
• Heads on the first toss, tails on the second toss.
• Heads on both tosses.

The difference is that the stars-and-bars interpretation is only counting the number of times each face showed without regard to when it showed.

In practice, a coin flipped two times has a $1/4$ probability to show heads both times, not a $1/3$ probability. This is consistent with the notion that each face is equally likely on the first toss, each face is equally likely on the second toss, and the face that shows on the second toss is independent of the face that shows on the first toss. Hence if we want to count equally-likely outcomes, we use the multinomial interpretation.

---

I note that you got your "stars and bars" from the Stack Exchange page How many ways can we write $N$ as a sum of $K$ strictly positive numbers? It's worth pointing out that the information on this page is completely correct: stars and bars give you the number of ways you can write $N$ as a sum of $K$ strictly positive integers. What is not correct is your inference that this has anything to do with the probabilities of a set of $K$ dice rolled some number of times. For example, there is exactly one way to make the sum $2$ and exactly one way to make the sum $3,$ but when you roll two six-sided dice the probability of the sum $3$ is twice the probability of the sum $2$.

Answer 2

Note that the Wikipedia article talks about the probability of counts for each side of a $k$-sided dice rolled $n$ times. When you roll a die, its chances of landing in each of $1-6$ is equiprobable, and the multinomial coefficient will help to give the probability for a particular pattern of throws.

For example, a pattern of $2,1,2,1,1,0,1,2,$ will have a probability of $\dfrac{\dbinom{10}{2,1,2,1,1,0,1,2}}{6^{10}}$

Stars and bars instead gives all possible ways of filling $1-6$, but these are not equiprobable, eg you can understand that if you roll a die $10$ times, getting all ten as $6's$ is much less probable than a more even distribution