# Put $N$ identical balls into $m$ different buckets, each bucket has at least one ball, how many ways?

Suppose $N>m$, denote the number of ways to be $W(N,m)$

### First method

Take $m$ balls out of $N$, put one ball at each bucket. Then every ball of the left the $N-m$ balls can be freely put into $m$ bucket. Thus we have: $W(N,m)=m^{N-m}$.

### Second method

When we are going to put $N$-th ball, we are facing two possibilities:

1. the previous $N-1$ balls have already satisfies the condition we required, i.e. each of $m$ buckets has at least one ball. Therefore, we can put the $N$-th ball into any bucket.

2. the previous $N-1$ balls have made $m-1$ buckets satisfies the condition, we are left with one empty bucket, the $N$-th ball must be put into that empty bucket. However, that empty bucket may be any one of the $m$ buckets.

Therefore, we have the recursion formula:

$$W(N,m) = m W(N-1,m) + m W(N-1,m-1)$$

It is obvious that the two methods are not identical, which one has flaws? I would like to know which part of the reasoning is wrong and I would also want to hear about the case when the balls are distinct.

• Why would there be an empty bucket for the N-th ball ? – Astyx Nov 5 '16 at 14:44
• That is a possible situation before putting $N$-th ball – fizis Nov 5 '16 at 14:47
• But then there could also be 2 empty buckets, or 3 empty buckets ... couldn't there ? – Astyx Nov 5 '16 at 14:49
• @Astyx you can't fill two empty buckets with a single ball. – fizis Nov 5 '16 at 14:52

First put $1$ ball into each of $m$ buckets.

Then you are left with $N-m$ balls.

Use stars and bars method. Arrange the remaining balls in a row. Add $m-1$ dividers. Compute number of ways to arrange the balls and dividers.

Number of ways is given by =$$\binom {(N-m)+(m-1)}{m-1}=\binom{N-1}{m-1}$$

• you mean first is wrong? – fizis Nov 5 '16 at 15:04
• That would appear to be the case. Try it for a small number, e.g. $N=5, m=3$ and see. – hypergeometric Nov 5 '16 at 15:07
• Yes both methods are wrong – Astyx Nov 5 '16 at 15:10
• @Astyx Do you really mean that? Does any one survive if the balls are distinct? If you can write a detailed answer about that, it would be great. – fizis Nov 5 '16 at 15:12
• @fizis: If the balls are distinct, then the number of possible arrangements would be a Stirling number of the second kind. – Edward Nov 5 '16 at 15:21

hypergeometric has given a good analysis of the problem for indistinguishable balls.

When the balls are distinct, we can number them $1$ through $N$. If we number the buckets $1$ through $m$, each assignment of balls to buckets with at least one ball in each bucket can be thought of as a function from the set $[N]=\{1,\ldots,N\}$ onto the set $[m]=\{1,\ldots,m\}$. That is, we’re counting the surjections from $[N]$ to $[m]$.

The Stirling numbers of the second kind are the key ingredient here: the Stirling number ${N\brace m}$ is the number of partitions of $[N]$ into $m$ non-empty parts. There are $m!$ ways to assign each of the parts to one of the $m$ numbers in $[m]$, so there are $m!{N\brace m}$ surjections from $[N]$ to $[m]$ and hence the same number of allowable assignments of the labelled balls to the labelled buckets. It turns out that

$$m!{N\brace m}=\sum_{k=0}^m(-1)^{m-k}\binom{m}kk^N\;,$$

a result that can also be obtained directly using the inclusion-exclusion principle. There is no really nice closed form for this number, though the Stirling numbers themselves do satisfy a fairly nice recurrence:

$${{n+1}\brace k}=k{n\brace k}+{n\brace{k-1}}\;,$$

with ${0\brace 0}=1$ and ${n\brace 0}={0\brace n}=0$ for $n>0$.

• How can we have the summation formula from the recursion formula? – fizis Nov 6 '16 at 3:05
• @fizis: That isn't how I would get it; the inclusion-exclusion argument is definitely the way to go. – Brian M. Scott Nov 6 '16 at 3:21
• Alright, I will look into it. – fizis Nov 6 '16 at 3:33
• Thank you - very kind of you :) Nice answer, extending this to distinct balls. (+1) – hypergeometric Nov 6 '16 at 16:41

The mistake comes form the fact that the two possibilities of the second method are not disjoint.

For instance when putting the 6-th ball in a set of three buckets, if you have $(1,2,2)$ you can get $(2,2,2)$, or $(1,3,2)$ or $(1,2,3)$.

If you had $(0, 3, 2)$ you need to get $(1,3,2)$ which is a way that has already been counted in the previous case.

• you mean second is wrong? – fizis Nov 5 '16 at 15:04
• Yes, this is what I mean – Astyx Nov 5 '16 at 15:07