I want to know how many ways I can place some, possibly all of five balls each a distinct color into 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 any way 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.
Best 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.