Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given 'a' identical objects of one kind and 'b' identical objects of other kind. Also, given 'k' indistinguishable buckets. In how many ways can one put the '(a+b)' objects into the 'k' buckets such that every bucket has atleast a single object?

As an example, let's suppose we have 3 As and 2 Bs and we need to partition them into 2 buckets. (a=3, b=2, k=2). The possible combinations are:

  1. A | AABB
  2. AA | ABB
  3. AAA | BB
  4. AAAB | B
  5. AAB | AB

So, there exist 5 such partitions.

share|improve this question
    
Does the ordering withing the bucket matter (i.e. order in which the objects are put in the bucket)? –  Aryabhata Apr 27 '12 at 21:41
    
No, the ordering within the buckets doesn't matter. –  nitzs Apr 27 '12 at 21:46
    
I just saw your example. You say the buckets are different (distinguishable), but your example does not seem to make it so. –  Aryabhata Apr 27 '12 at 23:23
    
Sorry, I didn't meant different as in distinguishable. The buckets are indistinguishable. –  nitzs Apr 28 '12 at 7:30

2 Answers 2

Arrange in the a + b objects in a line. One can get $\frac{(a + b)!}{a! b!}$ such arrangements. Then, by the bars and stars theorems, we know that we can partition the arrangement of a+b objects into k buckets in ${a+b-1\choose{k-1}}$ possible ways. Therefore, in total,$$\frac{(a + b)!}{a! b!}{a+b-1\choose{k-1}}$$

share|improve this answer
    
Won't this double count? $a| a bb$ and $a|b a b$ will be counted differently? (Assuming a bucket is a "multiset"). –  Aryabhata Apr 27 '12 at 21:41
    
@Aryabhata Good point! I guess I will have to sit on it a bit more. –  TenaliRaman Apr 27 '12 at 21:44

It would be surprising if a closed form could be given for this number, since setting $b=0$ would give the number of partitions of $a$ into $k$ parts, for which no closed form is known. But we can readily write down a generating function by analogy with the partition number generating function: The desired number is the coefficient of $x^ay^bz^k$ in

$$\prod_{{\scriptstyle l,m=0}\atop{\scriptstyle l+m\ne 0}}^\infty\frac1{1-x^ly^mz}\;.$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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