Combinations of multisets - the theory?

Question

I've read over the theory countless times, and I still have no idea how to think of it.

The formula for the combinations of multisets is $C(k + r - 1, r)$, where $k$ = the number of distinct elements, and $r$ is the $r$-combinations required.

Let's use an example.

If I have the set $S = \{2 \text{ of } 1, 1 \text{ of } 2, 1 \text{ of } 3\}$.

The possible combinations would simply be 1123, 1132, 1231, 1213, 1321, 1312, 2113, 2131, 2311, 3112, 3121, 3211

Which would equal to $12$.

But according to the formula, this should be $C(3 + 4 - 1, 4)$, or $C(6,4)$, or $15$.

Did I do something wrong here?

How do I fix this?

Can someone explain how this formula is derived?

Thanks! Baggio.

Answer 1

That's not the formula for what you're counting. You want the multinomial coefficient

$$ \pmatrix{r\\r_1,\dotsc,r_k}=\frac{r!}{r_1!\cdots r_k!}=\frac{4!}{2!1!1!}=12\;. $$

For explanations, see the "Interpretations" section of the article.

Answer 2

If you want to use binomial coefficients then your calculations should be

$${r \choose r_1}{r-r_1 \choose r_2}\cdots{r-r_1-r_2-\cdots-r_{k-1} \choose r_{k}}$$ which in your example is $${4 \choose 2}{4-2 \choose 1}{4-2-1 \choose 1} = 6 \times 2 \times 1 =12$$ i.e. with six choices over where to put the $1$s, then two choices where to put the $2$ and then one choice where to put the $3$.

Cancellation of factorials gives the same general multinomial result as joriki: $\dfrac{r!}{r_1!\cdots r_k!}$.

Answer 3

Henry and joriki have explained what calculations you should have used; I’ll give some examples of problems for which $\binom{k+r-1}r$ is the answer.

$\binom{k+r-1}r$ is the number of ways of distributing $r$ indistinguishable objects amongst $k$ distinguishable containers. Here are some problems that can be reformulated in such terms.

1. How many solutions in non-negative integers are there to the equation $x_1+\ldots+x_k=r$?

2. There are $k$ types of doughnuts on sale, and at least $r$ of each type are available. You ask for $r$ doughnuts, but you don’t specify how many of each type you want. In how many different ways can the baker fill your order? (Two ways are different if they differ in the number of doughnuts of some type.)

   • To reduce (2) to (1), let $x_i$ be the number of doughnuts of type $i$ that the baker uses to fill the order.

3. How many non-decreasing sequences $\langle a_1,\dots,a_k\rangle$ of non-negative integers are there such that $a_k=r$?

   • To reduce (3) to (1), let $x_1=a_1$, and let $x_i=a_i-a_{i-1}$ for $i=2,\dots,k$.

4. How many non-decreasing sequences $\langle a_1,\dots,a_{k-1}\rangle$ of non-negative integers are there such that $a_{k-1}\le r$?

   • To reduce (4) to (1), let $x_1=a_1$, $x_i=a_i-a_{i-1}$ for $i=2,\dots,k-1$, and $x_k=r-a_{k-1}$.

5. How many strictly increasing sequences $\langle a_1,\dots,a_{k-1}\rangle$ of positive integers are there such that $a_{k-1}<r+k$?

   • To reduce (5) to (1), let $x_1=a_1-1$, $x_i=a_i-a_{i-1}-1$ for $i=2,\dots,k-1$, and $x_k=r+k-a_{k-1}-1$.

6. How many strings of $k-1$ $0$’s and $r+k-2$ $1$’s are there in which the substring $00$ does not occur?

   • To reduce (6) to (1), let $x_1$ be the number of $1$’s before the first $0$, $x_i+1$ the number of $1$’s between the $(i-1)$-st and $i$-th $0$’s for $i=2,\dots,k-1$, and $x_k$ the number of $1$’s after the last $0$.

Finally, to see that (1) reduces to the original description, let $x_i$ be the number of objects in container $i$.

Answer 4

Here's a simpler answer using stars and bars method. You have a set S = {1,2,3} and you can choose 4 digits from S with duplicates as shown from your example. For example, the outcome can be 1112 or 1233 ...etc

Go through eat element in S and add a star to it if you would like to pick that digit. To have the output 1122, you do this:

1(star) (star) 2 (star) (star) 3

(you go through #1 and say you want to pick that digit 2 times, so put 2 stars next to it, and then at #2 you want to pick it, so you put 2 stars next to number 2).

To have an output 2233, you do this: 1 2 (star) (star) 3 (star) (star).

To have an output 1223, you do this: 1 (star) 2 (star) (star) 3 (star).

This is equivalent to C(6,4) = 15.

6 placements and you choose 4 placements for the stars (remove the number 1 to get 6 placements)