1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Multichoosing (Stars and bars)

  1. May 4, 2014 #1
    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)##.
     
  2. jcsd
  3. May 5, 2014 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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).
     
  4. May 5, 2014 #3
    The notation [itex]\left(\!\left(n \atop k\right)\!\right)[/itex] means [itex]\binom{n+k-1}{k}[/itex].

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

    Yes, [itex]\left(\!\left(n \atop k\right)\!\right)[/itex] is positive even when k > n. This makes sense, because you can pick a multiset that is larger than the original set.
     
  5. May 6, 2014 #4
    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.
     
  6. May 6, 2014 #5
    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}.
     
  7. May 7, 2014 #6
    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}. :confused:
     
  8. May 7, 2014 #7
    No. The number of multisets is ##\left(\!\left(n \atop k\right)\!\right)##, not ##\left(\!\left(k \atop n\right)\!\right)##.
     
  9. May 10, 2014 #8
    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)##.
     
    Last edited: May 10, 2014
  10. May 10, 2014 #9
    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)##.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Multichoosing (Stars and bars)
Loading...