3
$\begingroup$

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

  • 0
    [link](http://www.learnersdictionary.com/art/ld/basket.gif) and yes they are distinguishable. Let them be numerated from 1 to k. So it is a difference if there a 3 balls in basket 1 and 2 in basket 2 or 3 balls in basket 2 and 2 in 1.2012-12-05

1 Answers 1

1

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

  • 1
    +1: Henry is correct. To see why, group the balls into $m$ nonempty subsets in $S_2[n,m]$ ways. Then choose which of the $k$ baskets the first subset goes into, which of the remaining $k-1$ baskets the second subset goes into, and so forth, in $k!/(k-m)!$ ways.2012-12-05