Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question
2  
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
show 5 more comments

2 Answers 2

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.