Number of ways to put $m$ balls in $N$ bins with exactly one empty bin

Question

There are $N$ bins labelled $1,...,N$ and $m$ balls labelled $1,...,m$. How many ways are there of placing the $m$ balls into the $N$ bins (each bin can hold an arbitrary number of balls, and can be empty) if there must be exactly one empty bin?

I know in general, to put $m$ balls in $N$ bins, we can use the stars-and-bars principle; however in the case of one (or general $k$) empty bins how do we modify the stars-and-bars approach, or do we use a completely different method? (I've looked at the related questions and found this but looks to be for a very specific case of $N+1$ balls.)

Answer 1

One definition of the Stirling numbers of the second kind $S(n,k)$ is the number of ways to put $n$ labelled balls in $k$ unlabelled bins with no bin empty. Thus the answer to your problem is the product of

• choosing which bins are empty: $\binom nk$
• putting the balls in the "nonempty" bins: $S(m,n-k)$
• permuting the nonempty bins (thus accounting for the bins being labelled): $(n-k)!$

This gives $\frac{n!}{k!}S(m,n-k)$.