1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Multinomial coefficients are (almost, but not quite) option 3. Multiset coefficients are none of the above. $\endgroup$ – David K Aug 21 '17 at 3:20
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very thorough and very clear -- I greatly appreciate your help and this contribution. $\endgroup$ – Chill2Macht Aug 21 '17 at 4:17
-1
$\begingroup$

Motivation: Describing the number of monomials of degree $d$ in the variables $x_0, \dots, x_n$ requires the use of a multiset coefficient, not a multinomial coefficient. When I forget why, I have difficulty explaining to myself why the multiset coefficient works and why the multinomial one doesn't.

Background: According to Wikipedia, they are distinct, but I am having difficulty focusing in on the key aspects which differentiate them, as well as the key aspects which make them similar.

Unlike for binomial coefficients, there is no "multiset theorem" in which multiset coefficients would occur, and they should not be confused with the unrelated multinomial coefficients that occur in the multinomial theorem. (Source)

Multiset and multinomial coefficients are distinct, but even if they are not related to each other, they do appear to both be related to counting problems involving multisets.

  • n multichoose k is given by the simple formula

$$((n; k))=(n+k-1; k)=(n-1,k)!,$$ where (n-1,k)! is a multinomial coefficient. (Source)

  • The multinomial coefficients $$(n_1,n_2,...,n_k)!=\frac{((n_1+n_2+...+n_k)!)}{(n_1!n_2!...n_k!)} $$are the terms in the multinomial series expansion. In other words, the number of distinct permutations in a multiset of k distinct elements of multiplicity $n_i (1 \le i \le k)$ is $(n_1,...,n_k)!$ (Skiena 1990, p. 12). (Source)

  • A multinomial coefficient is associated with each (finite) multiset taken from the set of natural numbers. Such a multi-set is given by a list $k_1, . . . , k_n,$ where numbers may be repeated, and where order does not matter... The total number of such multi-indices is $(\binom{n}{k})$. The multi-index N determines a multi-set $k_1, . . . , k_n$ taken from the natural numbers. This multi-set consists of the values of the function N. It has less information in it than the multi-index $N$, since it has lost the information about which elements of $B$ index the numbers. (Source)

  • The number of multiset combinations equals the multinomial coefficient (n multichoose k). (Source)

My understanding currently is that the multinomial coefficient is the number of ways of assigning $n$ objects to $i$ containers with $k_i$ spots each and $k = \sum_i k_i$ spots total, where order matters.

This explanation makes sense to me inasmuch as it explains why the sum of all multinomial coefficients is $i^k = i^n$ when $k=n$. However, it doesn't make sense to me inasmuch as multinomial coefficients are supposed to be related to binomial coefficients, which are supposed to give the number of ways of choosing elements when order doesn't matter.

But if order doesn't matter for multinomial coefficients, it doesn't matter for multiset coefficients either, which doesn't leave a clear way to distinguish them:

A k-combination with repetitions, or k-multicombination, or multisubset of size k from a set S is given by a sequence of k not necessarily distinct elements of S, where order is not taken into account. (Source)

$\endgroup$
  • 1
    $\begingroup$ While it is interesting that "multichoose" comes out to a binomial coefficient (which is also therefore a multinomial coefficient), it's not exactly a direct correspondence: $\binom{n+k-1}{k},$ not $\binom nk.$ It's just one of those interesting mathematical marvels where something designed to do one thing can, with a little tweaking, be made to give the answer to a very different problem. $\endgroup$ – David K Aug 21 '17 at 3:10
  • 1
    $\begingroup$ By the way, it's kind of weird to write an "answer" that's really just a continuation of the question. $\endgroup$ – David K Aug 21 '17 at 3:12
  • $\begingroup$ @DavidK I agree, but (1) it's CW, so it doesn't matter and (2) the question was too long with this in the body, so no one was reading it. My priority is to get the question answered, not to worry about protocol. $\endgroup$ – Chill2Macht Aug 21 '17 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.