0
$\begingroup$

This one is hurting my brain. How many ways are there to distribute n distinct objects into r distinct groups of arbitrary sizes, when only one particular group is allowed (but not required) to be empty? Or, in other words, how many ways are there to spread n distinct objects across a number of labelled groups when you can put several objects into one group and don't have to use all objects?

I'm writing an algorithm where several objects have to be distributed over a number of baskets. If there are some baskets and a 0th basket to store the remainder, then it's easy to calculate the number of possible distributions when only the remainder can be an aggregate of multiple objects. Or, to put it differently, the number of possibilities of distributing the objects without using all of them when each basket can only store 1 object.

For example, if n = 7 and r = 3, then there are 7P3 = 210 ways to distribute the objects so that there is 1 object in each basket and 7-3=4 unused objects remaining in the 0th basket. However, I now need to know how to do the same thing when all baskets are allowed to contain multiple objects and require at least 1, where it is irrelevant if basket #0 (the remainder) contains objects or not.

Cheers.

$\endgroup$
  • $\begingroup$ The special basket is I think not the main difficulty, it is the others non-empty. Assume all baskets must be non-empty. Then for the number of functions we can use Inclusion/Exclusion. Whatever we do we bump into Stirling Numbers of the Second Kind (please see Wikipedia). No closed form, but there are useful recurrences. $\endgroup$ – André Nicolas Sep 17 '15 at 13:57
  • $\begingroup$ Right. It would require correcting for the fact that Stirling Numbers of the Second Kind assume unlabelled groups, no? $\endgroup$ – JGTP Sep 17 '15 at 14:57
  • $\begingroup$ If we are dumping into $k$ labelled groups, multiply the Stirling number by $k!$. $\endgroup$ – André Nicolas Sep 17 '15 at 15:07
  • $\begingroup$ So, k! S2(n,k)+(k-1)! S2(n,k-1) then? Combinatronics isn't really my thing, as you can tell. $\endgroup$ – JGTP Sep 18 '15 at 12:53
  • $\begingroup$ Yes, the onto functions plus the ones that leave the special basket empty, and there are $(k-1)S(n,k-1)$ of these. Would you like to write it up as an answer? If I am informed you have done it, and you have trouble with the LaTeX, I can do the formatting. $\endgroup$ – André Nicolas Sep 18 '15 at 13:17
2
$\begingroup$

For a number of objects $n$ and a number of labelled clusters $k$, the number of distributions $N$ equals: $$ N(n,k) = k! \cdot S_2(n,k) + (k-1)! \cdot S_2(n,k-1) $$ where $S_2(n,k)$ is the Stirling Number of the Second Kind.

$\endgroup$

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.