Combination math question: at least one box has only one ball, what is the number of this case?

Question

there are M same balls and K different boxes. the boxes are labeled from 1,2,...,K. each box could have any number of balls, or be empty.

the question is: at least one box has only one ball, what is the number of this case?

Answer 1

Theorem 2 of Stars and Bars allows for empty boxes. Now you could have only one box have one ball and this you could choose it in K ways. The rest you could use theorem 2. $ Thus, it is

${k\choose 1} [{{m-1+k-1-1}\choose {k-2}}]$.

Now you could have two boxes having only one ball and this you could choose it in ${k\choose 2}$ ways. The rest you could use theorem 2 again. This you subtract from the previous Thus it is ${k\choose 2} [{{m-2+k-2-1}\choose {k-3}}]$. Now you could have three boxes having only one ball and this you could choose it in ${k\choose 3}$ ways. The rest you could use theorem 2 again. This you add back from the previous Thus it is ${k\choose 3} [{{m-3+k-3-1}\choose {k-4}}]$. Keeps going until you have all the boxes to contain exactly only one ball in ${k\choose {m}}$ ways. ${k\choose {m}} [{{m-m+k-m-1}\choose {k-m-1}}]$ when k > m

You could add all and I think that will be the total number of ways you could have atleast one box contain only one ball which is

$${k\choose 1} [{{m-1+k-1-1}\choose {k-2}}]-{k\choose 2} [{{m-2+k-2-1}\choose {k-3}}]+{k\choose 3} [{{m-3+k-3-1}\choose {k-4}}]-\cdots+{k\choose {m}} [{{m-m+k-m-1}\choose {k-m-1}}]$$

$${k\choose 1} [{{m+k-3}\choose {k-2}}]-{k\choose 2} [{{m+k-5}\choose {k-3}}]+{k\choose 3} [{{m+k-7}\choose {k-4}}]\cdots+{k\choose {m}} [{{k-m-1}\choose {k-m-1}}]$$

Answer 2

There are $K \choose 1$ boxes that could have only one ball, and for each of those there are $K-1$ boxes to distribute the rest of the $M-1$ balls (counted by using the stars-and-bars principle with $K-2$ 'bars' and $M-1$ 'stars').

So far that's $\dbinom{K}{1}\dbinom{M+K-3 }{ M-1} = \dfrac{K!(M+K-3)!}{1!(K-1)!(M-1)!(K-2)!}$

However, to avoid double counting we must use the exclusion inclusion principle.  Subtract the ways to have two boxes with only one ball, add back those with three such boxes, etc. till you reach $K-1$ such boxes, or have used all $M$ balls.

$$ \sum_{i=1}^{\min(M,K-1)} \dfrac{(-1)^{i+1}K!(M+K-2-i)!}{i!(K-i)!(M-i)!(K-i-1)!}$$

Answer 3

It seems easier to count the number of ways of not having a single box with just one ball, and then subtract from the total way of putting $M$ balls in K different boxes, e.g., by using Stars and Bars : http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics) to get $(M+K-1)C(K-1)$. Throw 2 balls in each box, then you have $M-2K$ balls left. Now , use , e.g., Stars and Bars , to count the total number of ways of distributing $M-2K$ balls in $K$ boxes. Then subtract this last number from $(M+K-1)C(K-1)$.

EDIT: I think there is a problem in my answer; I assumed here that the negation of having at least one ball was having two-or-more balls, but I don't think that holds; the negation should include the case of boxes being empty. Please give me some time to think it through and rewrite; I will delete if I don't come up with anything soon.

Answer 4

There are $K$ ways in which you can choose the box with only one ball. It then leaves you with $M-1$ balls and $K-1$ boxes. Use the Stars and bars analogy given by user99680 to get the number of ways in which you can throw $M-1$ balls into $K-1$ boxes without constraints, and then multiply it by $K$ to get the answer to your question.