2
$\begingroup$

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.

  • 0
    Thank $y$ou for that webpage. Very useful indeed.2010-12-19

1 Answers 1

3

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?

  • 1
    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).2010-12-20