Combinations of multisets - the theory?
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.
Solution 1:
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.
How many solutions in non-negative integers are there to the equation $x_1+\ldots+x_k=r$?
-
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.
-
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$.
-
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}$.
-
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$.
-
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$.
Solution 2:
Suppose you have some set S made up of k = 3 distinct objects: {1, 2, 3}. (Note that |S| might be strictly greater than k.)
Then the formula you mentioned, C(k + r - 1, r), comes in when you want to know the number of ways of choosing r objects from S, but only if your set S includes at least r duplicates of each of your distinct objects. That is, if r = 2, then the set {1, 1, 2, 2, 3, 3} must be a subset of S.
So for your original set, S = {1, 1, 2, 3}, the formula C(k + r - 1, r) only applies for counting the ways of choosing r objects from S if r = 1.
(Just to be clear, your list of {1123, 1132, 1231, 1213, 1321, 1312, 2113, 2131, 2311, 3112, 3121, 3211} is the set of all possible permutations of S, not the number of combinations.)
Hope this helps!
Solution 3:
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.
Solution 4:
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!}$.