# 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.

Thanks in advance.

-
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

## 1 Answer

These are the Stirling numbers of the second kind. I am not sure what you mean by a famous problem that this sequence solves; you seem to already have given the standard combinatorial interpretation.

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: are you sure that "partitions of an n-element set into k non-empty subsets" isn't the "famous problem" that you read about? – Qiaochu Yuan Dec 18 '10 at 1:26
@Robert, @Qiaochu: Could the "famous problem" be the problem of enumerating the partitions of $n$? – Arturo Magidin Dec 18 '10 at 2:25
@Arturo: I'm not sure. It could be, though. Can you state the conditions for such enumeration? – Robert Smith Dec 18 '10 at 3:41
For completeness: Stanley's Enumerative Combinatorics contains several identities dealing with the Stirling numbers of the second kind in pages 33-35. Flajolet's Analytic Combinatorics provides some properties in pages 59-60 and a brief explanation in page 100. Additionally, I found a very nice chapter of combinatorics in Harris and Hirst's Combinatorics and graph theory (page 231 for a survey on the Stirling numbers). – Robert Smith Dec 20 '10 at 23:21