2
$\begingroup$

I need to proof the following formula for Stirling Numbers of the Second Kind:

$\sum\limits_{n \geq 0} S(n,k) x^n = \frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}$

It is used widely around formularies but I neither have found any proof nor was I able to figure it out on my own.

Could you please help me finding a solution?

Thank you in advance!

  • 2
    How do you define Stirling numbers?2011-05-14
  • 0
    For $n \geq1, k \geq 0$ is $c(n,k)$ the quantity of permutations $\pi \in S_n$ having k cycles. c(0,0) := 1, c(0,k) := 0 for $k \geq 1$. Set for $m,n \geq 0$ $s(m,n) := (-1)^{m-n}c(m,n)$ The numbers $s(m,n)$ alre called Stirling Numbers of the First Kind.2011-05-14
  • 0
    @thewilli So why is there a capital S in your formula?2011-05-14
  • 0
    Hmm, our prof seems to use other conventions that the guy writing the lecture notes. It definitely is the same..2011-05-14
  • 0
    No, it isn't....2011-05-14
  • 0
    They didn't provide an alternative definition. So what's the mistake here?2011-05-14
  • 0
    What makes you think that $S(n,k)$ are the Stirling numbers of the first kind?2011-05-14
  • 0
    My course tutor who told me so when talking about that excercise (That does not necessarily mean he's right, but most times he is)2011-05-14
  • 0
    $S(n,k)$ denotes the Stirling numbers of the second kind, and you should look up all definitions in an exercice that are not very well-known to you.2011-05-14
  • 0
    It's identity (15) here http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html2011-05-14

2 Answers 2

1

This is set out in the initial part of section 1.6 of Geneatingfunctionology with the result in equation 1.6.5.

In essense, you start with the recurrence

$$S(n,k) = S(n-1,k-1) + kS(n-1,k)$$

with $S(0,0)=1$. Of the natural generation functions which might express this, the simplest which deals with the factor of $k$ is likely to be of the form

$$B_k(x) = \sum_n S(n,k) x^n$$

which with the recurrence leads to

$$B_k(x) = xB_{k-1}(x) + kxB_k(x) = \frac{x}{1-kx} B_{k-1}(x)$$

for $k \ge 1$; $B_0(x)=1$. That in turn leads to the desired formula by multiplying successive terms.

  • 0
    could you please explain me what you did in the last step ($\cdots = \frac{x}{1-kx}B_{k-1}(x)$)?2011-05-15
  • 0
    If $B_k(x) = xB_{k-1}(x) + kxB_k(x)$ then $B_k(x) - kxB_k(x)= xB_{k-1}(x)$, i.e $(1- kx)B_k(x)= xB_{k-1}(x)$, so $ B_k(x) = \frac{x}{1-kx} B_{k-1}(x)$2011-05-15
3

Hmm, I cannot see the problem which came up in the comments. If we assume simply an error in the notation and that the actually the Stirling numbers 2'nd kind are meant (as verbally exposed in the question) then the identity holds. This can even be checked simply using negative integer $x$ and computing Eulersums of appropriate order.
Let's write S2 the matrix of that numbers as
$ \qquad \small \begin{array} {rrrrrrr} 1 & . & . & . & . & . & . & . \\ 1 & 1 & . & . & . & . & . & . \\ 1 & 3 & 1 & . & . & . & . & . \\ 1 & 7 & 6 & 1 & . & . & . & . \\ 1 & 15 & 25 & 10 & 1 & . & . & . \\ 1 & 31 & 90 & 65 & 15 & 1 & . & . \\ 1 & 63 & 301 & 350 & 140 & 21 & 1 & . \\ 1 & 127 & 966 & 1701 & 1050 & 266 & 28 & 1 \\ \ldots & \end{array} $
where we use zero-based row- and columnindexes.

Then the problem can be restated as summing by building the dot product of one column by one row vector $V(x) = [1,x,x^2,x^3,...]$ with manageable (ideally infinite) dimension.

The numbers along a column can be seen as composed by finite compositions of geometric series.

Column 0 is $[1,1,1,1,1,...]$ and the dot-product with the V(x)-vector is then $V(x)*S2[,0] = {1 \over 1-x}$

Column 1 is $[1-1,2-1,4-1,8-1,16-1,...]$ and the dot-product with the V(x)-vector is then $V(x)*S2[,1] = {1 \over 1-2x} - {1 \over 1-x} = { (1-1x) - (1-2x) \over (1-1x)(1-2x) } = {x \over (1-1x)(1-2x) }$

One needs the simple composition of the other columns (see for instance in wikipedia) to see more examples for that decompositions, and also a general description for that compositions (where the text is:"Another explicit expanding of the recurrence-relation(...)").
I think the idea behind that homework-assignment was, that the student should find the compositions of powers such that the problem is ocnverted to describe the (finite) composition of closed forms of geometric series.