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.

  • 2
    Quick note: both are correct; what does the $\nu=n$ term in the sum look like?2010-12-18
  • 0
    Ha, right... thanks!2010-12-18
  • 0
    $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?2010-12-18
  • 0
    @Mike: I don't think so, unless that behind that interpretation remains an old and famous problem.2010-12-18
  • 1
    There are a lot of references and some formulas for these numbers in the OEIS: http://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.2010-12-18
  • 0
    Thank you 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?

  • 0
    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?).2010-12-18
  • 0
    @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?2010-12-18
  • 0
    @Robert, @Qiaochu: Could the "famous problem" be the problem of enumerating the partitions of $n$?2010-12-18
  • 0
    @Arturo: I'm not sure. It could be, though. Can you state the conditions for such enumeration?2010-12-18
  • 0
    @Qiaochu, Arturo: It's not strictly necessary to know which problem was solved by this solution (although, I would be nice). I could very well be satisfied with a good treatment on this particular expression.2010-12-18
  • 0
    @Robert: what do you mean by a good treatment? What, exactly, do you want to know?2010-12-18
  • 0
    @Qiaochu: Not much... A nice introduction and a few identities.2010-12-18
  • 0
    @Robert: there might be a discussion in Stanley's _Enumerative Combinatorics_; I am pretty sure there is a discussion in Flajolet and Sedgewick's _Analytic Combinatorics_. These numbers show up implicitly in a recent math.SE question (http://math.stackexchange.com/questions/14245/formal-proof-of-exponential-rule/14251#14251) as the coefficients of (exp(x) - 1)^n, and they also have a somewhat interesting ordinary generating function. Finally, they allow you to write down the generating function sum n^k x^n "explicitly," which leads to the application I mentioned.2010-12-18
  • 0
    Great! I'm going to take a look at those references.2010-12-18
  • 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