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.
Best Answer
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.