# About the Stirling number of the second kind

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.

-
Well, first off, it might be helpful if you wrote the corresponding variables in the same spot. $n$ is in the first spot once and second spot the other time. Next, note as $k$ runs from $0$ to $n$, $n-k$ runs from $n$ to $0$. So, if you're off, it's the $\frac{1}{n!}$ in the second answer that is not in your answer. – Graphth Nov 6 '11 at 15:49
I think it should be mentioned that the objects are distinguishable but the boxes are not. If the boxes were distinguishable the problem of finding the Stirling numbers would be simpler. – Michael Hardy Nov 6 '11 at 17:35

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)$.