Counting ways to distribute $n$ balls into $k$ baskets with the Stirling numbers of the second kind

301 Views Asked by At

How many options are there to distribute $n$ balls into $k$ baskets, so there are exactly $m$ baskets with at least 1 ball and the other $k-m$ baskets are empty?

I defined a function: $W[n, k, m] = S_2[n, m]k! - k((k - m)! - 1)$ but I am not sure if it is correct.

A few examples:

$$W[4, 3, 1] = 3$$ $$W[4, 3, 2] = 42$$ $$W[4, 3, 3] = 36$$

Regards

1

There are 1 best solutions below

1
On BEST ANSWER

Your solution does not seem to work for other values of $n,k,m$.

For example putting four balls into exactly two of four boxes, I think there are ${4 \choose 2}(2^4 -2)=84$ ways, but substituting $n=4, k=4, m=2$ into $S_2[n, m]k! - k((k - m)! - 1) $ gives $$S_2[4, 2] \times 4! - 4\times ((4 - 2)! - 1) = 7 \times 24 - 4\times (2-1) = 164.$$

I think the solution may be the simpler $$W[n,k,m] = S_2[n,m] \frac{k!}{(k-m)!}$$

and again letting $n=4, k=4, m=2$ $$W[4,4,2] = S_2[4,2] \times \frac{4!}{(4-2)!} = 7 \times \frac{24}{2}=84.$$