Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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 Answer 1

up vote 4 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.