# Number of distributions leaving none of $n$ cells empty

The solution for the number of distributions leaving none of the $n$ cells empty (with unlike cells and $r$ unlike objects) is given by

$$A(r,n)=\sum_{\nu=0}^{n-1}(-1)^{\nu}\binom{n}{\nu}(n-\nu)^{r}$$ (although I have seen the same expression summing from $\nu=0$ to $n$).

By the way, if anyone knows which one is correct, please let me know. However, that's not the question.

I have read that this expression provides a solution to a famous problem. I'd like to know where can I find more information about this solution and which famous problem solves. I already tried An Introduction to Combinatorial Analysis by John Riordan and Certain distributions of unlike objects into cells by Morton Abramson but their treatment of this particular expression is very brief.

-
Quick note: both are correct; what does the $\nu=n$ term in the sum look like? –  Steven Stadnicki Dec 18 '10 at 0:46
Ha, right... thanks! –  Robert Smith Dec 18 '10 at 1:02
$A(r,n)$ gives the number of onto functions from an $r$-element set to an $n$-element set; is that what you're looking for? –  Mike Spivey Dec 18 '10 at 2:35
@Mike: I don't think so, unless that behind that interpretation remains an old and famous problem. –  Robert Smith Dec 18 '10 at 3:43
There are a lot of references and some formulas for these numbers in the OEIS: oeis.org/A019538. In general, when you have some numbers that you're interested in learning more about, the OEIS is a great place to start looking. –  Mike Spivey Dec 18 '10 at 6:45
show 1 more comment

The Stirling numbers of the second kind occur in a certain formula for the sum $\sum_{k=1}^n k^r$; perhaps that's the problem you're thinking of?
Thank you for your answer. Yes, I know these are the Stirling numbers of the second kind (actually, Riordan gives the expression above with those numbers). Unfortunately, I'm looking for information not explicitly stated in terms of $S(n,k)$. Regarding the formula you wrote, no, I didn't have in mind that (now that you mention $\sum_{k=1}^n k^r$, to which famous problem that expression refers?). –  Robert Smith Dec 18 '10 at 1:11
@Robert, @Qiaochu: Could the "famous problem" be the problem of enumerating the partitions of $n$? –  Arturo Magidin Dec 18 '10 at 2:25