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:
-
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.
-
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.
Best Answer
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}$$