# Number of ways of partitioning $a+b$ objects into $k$ partitions such that every partition has at least one object

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.

• 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

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_{{l,m=0}\atop{l+m\ne 0}}^\infty\frac1{1-x^ly^mz}\;.$$
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}}$$
• 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