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.

  • 0
    Sorry, I didn't meant different as in distinguishable. The buckets are indistinguishable.2012-04-28

2 Answers 2

1

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

0

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

  • 0
    @Aryabhata Good point! I guess I will have to sit on it a bit more.2012-04-27