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:


*

*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.
 A: 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}$$
A: 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$.
A: 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.
