4
$\begingroup$

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.

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

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}\;.$$

$\endgroup$
0
$\begingroup$

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}}$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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