Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Balls distinguishable or not? Baskets? –  Henry Dec 5 '12 at 8:34
    
link 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. –  Frank_Martin Dec 5 '12 at 8:39
add comment

1 Answer 1

up vote 1 down vote accepted

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

share|improve this answer
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. –  Mike Spivey Dec 5 '12 at 23:49
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.