combinatorics - How to remember the difference between "stars and bars" and multinomial coefficients?

Explanation: It is easy for me to remember the difference between permutation coefficients and combination coefficients verbally: one says that the former

"is the number of ways of choosing $k$ things from $n$ options without replacement where order matters"

and that the latter

"is the number of ways of choosing $k$ things from $n$ options without replacement where order doesn't matter".

Question: How can one quickly describe (verbally) the difference between multinomial coefficients and "stars and bars" (which will here henceforth be called multiset coefficients)? For which does order matter? For which does order not matter? For which is the choosing with/without replacement?

Attempt: Both involve a counting process with two considerations: (i) dividing objects of $n$ types into $i$ containers, (ii) each container with $k_i$ spots, so assigning $k = \sum_i k_i$ objects from the $n$ different types. So it seems like there might be some ambiguity, when one says "with/without replacement" or "order does/doesn't matter", is one referring to (i) or (ii)?

So it seems like there are at least four distinct possibilities:

1. Assign $n$ types of object into $i$ containers, where the order of the containers doesn't matter, with $k = \sum_i k_i$ spots total, where the order within each container doesn't matter.


2. Assign $n$ types of object into $i$ containers, where the order of the containers doesn't matter, with $k = \sum_i k_i$ spots total, where the order within each container does matter.


3. Assign $n$ types of object into $i$ containers, where the order of the containers does matter, with $k = \sum_i k_i$ spots total, where the order within each container doesn't matter.


4. Assign $n$ types of object into $i$ containers, where the order of the containers does matter, with $k = \sum_i k_i$ spots total, where the order within each container does matter.

IF this is true, then which of these options corresponds to multinomial coefficients, and which of these options corresponds to multiset coefficients?

Update: I think the difference is this: "multiset coefficients are the number of ways of distributing balls into boxes, where (i) the total number of balls is fixed, (ii) the number of balls in each container is not fixed, (iii) the balls are indistinguishable (their order doesn't matter, just the number in each container), (iv) the boxes are distinguishable (i.e. their order does matter)". (For (iv), e.g. $x^2 y \not= x y^2$.) While "multinomial coefficients are the number of ways of distributing balls into boxes, where (i) the total number of balls is fixed because (ii) the number of balls in each box is fixed, (iii) the balls are indistinguishable (hence the relationship to binomial coefficients), and (iv) the boxes are distinguishable (but it doesn't matter in the case of binomials because the solution to the Diophantine equation $k_1 + k_2 = k$ is already determined once $k_1$ is chosen)".

So TL;DR: in both cases, the balls are indistinguishable (their order doesn't matter), the boxes are distinguishable (their order does matter), the total number of balls is fixed, but (a) for multiset coefficients, the number of balls in each box is not fixed in advance, while (b) for multinomial coefficients the number of balls in each box is fixed in advance.

Thus the difference is whether one fixes in advance how many balls are to be placed into each box.

Answer

A multinomial coefficient is often written in the form $$ \binom{n}{k_1,k_2,\ldots,k_m} $$ where $k_1+k_2+\cdots+k_m = n.$ Because of that last equation, the $n$ is redundant. Binomial coefficients are technically multinomial coefficients as well, but instead of writing $\binom{n}{k_1,k_2}$ where $k_1+k_2 = n,$ we usually write either $\binom{n}{k_1}$ or $\binom{n}{k_2}.$ These are all mean exactly the same thing: $$ \binom{k_1+k_2}{k_1,k_2}=\binom{k_1+k_2}{k_1} =\binom{k_1+k_2}{k_2} = \frac{(k_1+k_2)!}{k_1!\,k_2!}. $$

A multinomial coefficient can arise in a counting problem as follows:

• You have $m$ containers, with sizes $k_1, k_2, \ldots, k_m$ respectively.


• You have $n = k_1+k_2+\cdots+k_m$ distinguishable objects, which are just enough to fill every container when drawing from the $n$ objects without replacement.


• The order of the containers matters.



• The order of the objects within each container does not matter.

---

A multiset coefficient can arise as follows:

• You have $n$ distinguishable objects.


• You have a single container able to hold $k$ objects.


• You draw objects from the $n$ objects with replacement, and put the copies of those objects into the container.


• You continue putting copies of objects in the container until it is full.


• The order of objects in the container does not matter.

A multiset coefficient can alternatively arise this way:

• You have $k$ objects that are indistinguishable or that you choose not to distinguish.


• You have $n$ containers, each with effectively infinite capacity (they never get full).



• You draw the objects without replacement and put them in the containers.


• The order of the containers matters.


• The order of objects in a container cannot matter, because by assumption you cannot tell which object is which, only how many are in each container.

These are two quite different ways of modeling a multiset coefficient: in one model, the number of objects is the first number of the coefficient, while in the other model the number of objects is the second number. But there is a simple counting argument that shows both ways model the same total count: each time you choose one of the $n$ objects in the first model to occupy one of the $k$ unordered (hence indistinguishable) places in the container, you choose one of the $n$ containers in the second model to hold one of the $k$ indistinguishable objects. Just as the first model allows you to choose the same object as often as you want (until all spaces in the container are full), the second model allows you to put objects in the the same container as many times as you like (until all objects have been placed).

While the term "multiset" is inspired by the first model, the second model is a frequent application of the "stars and bars" method. It's useful to know how to apply the multiset coefficient to either model as needed.