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.

I want to know how many ways I can place some, possibly all of five balls each a distinct color in to three distinguishable bins. Each bin must have at least one ball and I do not need to use all of the balls.

The numbers are small so I consider the cases:

(x,y,z) is the number of items in each bin. With only 5 items to use (at most) I have these possibilities:

(1,1,1) (5*4*3)/(1!1!1!)

(2,1,1) (5*4*3*2)/(2!1!1!)

(1,2,1) (5*4*3*2)/(2!1!1!)

(1,1,2) (5*4*3*2*1)/(2!1!1!)

(2,2,1) (5*4*3*2*1)/(2!2!1!)

(1,2,2) (5*4*3*2*1)/(2!2!1!)

(2,1,2) (5*4*3*2*1)/(2!2!1!)

(3,1,1) (5*4*3*2*1)/(3!1!1!)

(1,3,1) (5*4*3*2*1)/(3!1!1!)

(1,1,3) (5*4*3*2*1)/(3!1!1!)

Then take the total of the right column. I first count the ways of putting the balls in as if order mattered, then divide by the number of arrangements possible of balls that are grouped together in each of the three bins to account for repeats.

That's not a bad process for small numbers, but is there anyway to streamline this to solve the problem?:

How many ways I can place some, possibly all of n balls each a distinct color in to m distinguishable bins? Each bin must have at least one ball and I do not need to use all of the balls.

share|improve this question

2 Answers 2

Say that you have $n$ balls and $m$ bins, obviously with $n\ge m$. If you did not have the requirement that each bin receive at least one ball, there would be $(m+1)^n$ possible outcomes: for each of $n$ balls you choose a specific bin or set it aside, for a total of $m+1$ choices. Now we need only count the ‘bad’ distributions, i.e., those that leave at least one bin empty.

The same reasoning that we just used shows that there are $m^n$ distributions that leave bin $1$ (say) empty; since there are $m$ bins, this comes to a total of $m(m^n)=m^{n+1}$ distributions that leave at least one bin empty. Unfortunately, we’ve counted any distribution that omits two bins twice, so we have to compensate by adding $(m-1)^n$ ‘doubly bad’ distributions for each of the $\binom{m}2$ pairs of bins.

In short, this is an inclusion-exclusion problem, and the final result is

$$\begin{align*}(m+1)^n-\binom{m}1m^n+\binom{m}2(m-1)^n-\dots&=\sum_{k=0}^m(-1)^k\binom{m}k(m+1-k)^n\\ &=\sum_{k=0}^m(-1)^{m-k}\binom{m}k(k+1)^n\;. \end{align*}$$

share|improve this answer

Here's another way that seems a little slicker for the example, though I don't know which method scales up better.

Create a 4th bin for the balls you don't use. There are $4^5$ ways of putting the 5 balls into the 4 bins. Now use inclusion-exclusion; subtract the ones where one of the three bins is empty, add back in the ones where two bins are empty, subtract the ones where all three bins are empty. I get $$4^5-3\times 3^5+3\times2^5-1^5$$

EDIT: To relate this to well-studied concepts, the number of ways to put $n$ distinguishable balls into $m$ distinguishable bins, if you have to use all the balls and leave no bin empty, is $m!S(n,m)$, where $S(n,m)$ are the Stirling numbers of the second kind, q.v.

Now if you don't use all the balls, that's the same as putting the unused balls into an extra bin. So the answer to your problem is $$m!S(n,m)+(m+1)!S(n,m+1)$$

There is much information on Stirling numbers in books and online.

share|improve this answer

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.