Multichoosing (Stars and bars)

[22990atinesh]

Suppose we have 'n' Stars and 'k' bins. We have to distribute 'n' stars in 'k' bins (using k-1 bars) such that bins can be empty. We can do this in $\binom {n+k-1}{k-1}$ = $\binom {n+k-1}{n}$ ways. But Sometimes we use another notation $\left({{k}\choose {n}}\right)$ to represent $\binom {n+k-1}{k-1}$, Which says 'k multichoose n'. But normally as n > k, then how can we choose more objects from less objects i.e. n from k. So, I think It has to be like this $\left({{n}\choose {k}}\right)$.

 

[mfb]

You always choose (not "multichoose" here!) some objects from n+k-1 objects, which is not smaller than n or k (assuming n,k>0).

 

[eigenperson]

The notation $\left(\!\left(n \atop k\right)\!\right)$ means $\binom{n+k-1}{k}$.

The reason for this notation is that $\binom{n}{k}$ counts the number of sets of size k drawn from a universe of size n, whereas $\left(\!\left(n \atop k\right)\!\right)$ counts the number of multisets of size k drawn from a universe of size n.

Yes, $\left(\!\left(n \atop k\right)\!\right)$ is positive even when k > n. This makes sense, because you can pick a multiset that is larger than the original set.

 

[22990atinesh]

The notation $\left(\!\left(n \atop k\right)\!\right)$ means $\binom{n+k-1}{k}$.

The reason for this notation is that $\binom{n}{k}$ counts the number of sets of size k drawn from a universe of size n, whereas $\left(\!\left(n \atop k\right)\!\right)$ counts the number of multisets of size k drawn from a universe of size n.

Yes, $\left(\!\left(n \atop k\right)\!\right)$ is positive even when k > n. This makes sense, because you can pick a multiset that is larger than the original set.

I understand that $\binom{n}{k}$ counts the number of sets of size k. But I'm not getting what does $\left(\!\binom {k}{n}\!\right)$ represents. Can you please elaborate.

 

[eigenperson]

It counts the number of multisets of size k. A multiset is an object like a set, except that elements can appear more than once. The elements are required to be integers between 1 and n.

For example, if n = 3, the multisets of size 2 are {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}, and the multisets of size 3 are {1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}, {1, 3, 3}, {2, 2, 2}, {2, 2, 3}, {2, 3, 3}, {3, 3, 3}.

 

[22990atinesh]

It counts the number of multisets of size k. A multiset is an object like a set, except that elements can appear more than once. The elements are required to be integers between 1 and n.

For example, if n = 3, the multisets of size 2 are {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}, and the multisets of size 3 are {1, 1, 1}, {1, 1, 2}, {1, 1, 3}, {1, 2, 2}, {1, 2, 3}, {1, 3, 3}, {2, 2, 2}, {2, 2, 3}, {2, 3, 3}, {3, 3, 3}.

If n=3, the multisets of size 2 (k=2) is $\left(\binom {k}{n}\right)=\left(\binom {2}{3}\right)=\binom {3+2-1}{3}=\binom {4}{3}=4$. But we are getting 6 multisets {1, 1}, {1, 2}, {1, 3}, {2, 2}, {2, 3}, {3, 3}.

 

[eigenperson]

No. The number of multisets is $\left(\!\left(n \atop k\right)\!\right)$, not $\left(\!\left(k \atop n\right)\!\right)$.

 

[22990atinesh]

No. The number of multisets is $\left(\!\left(n \atop k\right)\!\right)$, not $\left(\!\left(k \atop n\right)\!\right)$.

Ok eigenperson I agree, If n=3, the multisets of size 2 (k=2) is $\left(\!\left(n \atop k\right)\!\right) = 6$. If we talk about this in terms of stars and bars, then what does 'n' and 'k' represents here. Can u explain the multi-set example in terms of stars and bars, It will clear my doubt.

Actually I've read this topic like this. Suppose we have 'n' Stars and 'k' bins.

Case I: We have to distribute 'n' stars in 'k' bins (using k-1 bars) such that bins can not be empty. We can do this in $\binom{n-1}{k-1}$ ways.
Case II: We have to distribute 'n' stars in 'k' bins (using k-1 bars) such that bins can be empty. So here we mix 'k' artificial indistinguishable extra stars with original 'n' stars making total of 'n+k' stars and reduce the problem to Case I. Hence there are $\binom{(n+k)-1}{k-1}$ ways to do it which is equal to $\left(\!\left(k \atop n\right)\!\right)$ not $\left(\!\left(n \atop k\right)\!\right)$.

 

[eigenperson]

To count the number of k-element multisubsets of an n-element set using balls and bins, first make a "bin" for each element in the set. (In this case, there are n bins. Your version of the problem uses the notation "k" for the number of bins, which I think is the source of the confusion.) Then put a number of balls in the bin equal to the number of times that element appears in the set. There are allowed to be a total of k balls. It is easy to translate between the multiset problem and the balls-and-bins problem in this way, but make sure you keep "n" and "k" straight.

Since, as you correctly state, the solution to the balls-and-bins problem is $\left(\!\left(\#bins \atop \#balls\right)\!\right)$, the number of k-element multisubsets of an n-element set is $\left(\!\left(n \atop k\right)\!\right)$.