About the Stirling number of the second kind

Question

Find the exponential generating function for $s_{n,r}$, the number of ways to distribute $r$ distinct objects into $n$ distinct boxes with no empty box, and determine $s_{n,r}$.

My solution is $$\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)^n=(e^x-1)^n$$ $$=\sum_{k=0}^n(-1)^k\binom{n}{k}e^{kx}=\sum_{k=0}^n(-1)^k\binom{n}{k}\sum_{r=0}^{\infty}k^r\frac{x^r}{r!}$$ Thus, $s_{n,r}$ is the coef. of $\frac{x^r}{r!}$, which is $\sum_{k=0}^n(-1)^k\binom{n}{k}k^r$.

However, I found it in another book that $s_{m,n}=\frac{1}{n!}\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^m$, where $s_{m,n}$ denotes the Stirling number of the second kind.

I was wondering what's wrong with my solution.

Answer 1

There are a couple of things going on here.

1. You should have $\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^r$ as the final answer. This is because you should have had $\sum_{k=0}^n(-1)^{n-k}\binom{n}{k}e^{kx}$ when you expanded $(e^x-1)^n$.
2. The question as you posed it is not asking about the Stirling numbers of the second kind. As Michael Hardy points out in a comment, the Stirling numbers of the second kind count the number of ways to distribute $r$ distinct objects into $n$ indistinguishable boxes. (Often this is phrased as "sets" rather than "indistinguishable boxes," as the former seems clearer.) Your question involves distinct boxes.

Let's expand on the second issue, as the two problems are clearly related. Since there's some notational confusion going on, let's let $T(r,n)$ denote the number of ways to distribute $r$ distinct objects into $n$ distinct boxes with no empty box (i.e., your problem), and we'll let $S(r,n)$ denote the number of ways to distribute $r$ distinct objects into $n$ indistinguishable boxes with no empty box. Then we have the relationship $T(r,n) = n! S(r,n)$. This is because the indistinguishable boxes can be made distinguishable by applying $n$ different labels to them, and there are $n!$ ways to assign $n$ labels to $n$ boxes.

This fits with your computations above. Your (corrected) computations have $$T(r,n) = \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}k^r.$$ The formula you cite for the Stirling numbers of the second kind has $$S(r,n) = \frac{1}{n!}\sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)^r.$$ Since $\binom{n}{n-k} = \binom{n}{k}$, though, by reindexing the sum we get $$S(r,n) = \frac{1}{n!}\sum_{k=0}^{n}(-1)^{n-k}\binom{n}{k}k^r,$$ in agreement with the argument above that $T(r,n) = n!S(r,n)$.