# Proving function for Stirling Numbers of the Second Kind

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.

-
How do you define Stirling numbers? – Phira May 14 '11 at 11:07
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. – muffel May 14 '11 at 11:15
@thewilli So why is there a capital S in your formula? – Phira May 14 '11 at 11:33
Hmm, our prof seems to use other conventions that the guy writing the lecture notes. It definitely is the same.. – muffel May 14 '11 at 11:39
No, it isn't.... – Phira May 14 '11 at 12:00

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

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

-
could you please explain me what you did in the last step ($\cdots = \frac{x}{1-kx}B_{k-1}(x)$)? – muffel May 15 '11 at 18:50
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)$ – Henry May 15 '11 at 21:24

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.

-