# Define term using Stirling Numbers

I am trying to solve the following exercise - quite unsuccessful yet.

Let a(m,n) be defined as $$\sum\limits_{n=0}^m a(m,n) \prod\limits_{i=1}^n (x+i-1) = x^m$$ Express a(m,n) using S(m,n) while S(m,n) are the Stirling numbers of the second kind which count the number of ways to partition a set of n elements into k nonempty subsets.

Hint: use the following identity : $$x^m = \sum\limits_{n=0}^m S(m,n) \cdot x \cdot (x-1) \cdots (x-n + 1)$$

First I rewrote the "hint"-identity as $$x^m = \sum\limits_{n=0}^m S(m,n) \prod\limits_{i=1}^n (x+1-i)$$

and got $$m = 0 \rightarrow a(0,0) = x^0 = S(0,0)$$ $$m = 1 \rightarrow a(1,0) + a(1,1) \cdot x = S(1,0) + S(1,1) \cdot x$$ and m = 2 $$a(2,0) + a(2,1) \cdot x + a(2,2) \cdot x \cdot (x+1) = S(2,0) \cdot x + S(2,1) \cdot x + S(2,2) \cdot x \cdot (x-1)$$ and both compared for m = 3 $$\begin{array}{llll} a(3,0) & + a(3,1) \cdot x & + a(3,2) \cdot x \cdot (x+1) & + a(3,3) \cdot x \cdot (x+1) \cdot (x+2) \\ \underbrace{S(3,0) \cdot x}_{\text{always 0}} & +S(3,1) \cdot x & +S(3,2) \cdot x \cdot (x-1) & +S(3,3) \cdot x \cdot (x-1) \cdot (x-2) \end{array}$$

Replacing x with -x in the "hint"-identity as recommended by user9325 results in

$$\begin{array}{llll} a(3,0) & + a(3,1) \cdot x & + a(3,2) \cdot x \cdot (x+1) & + a(3,3) \cdot x \cdot (x+1) \cdot (x+2) \\ S(3,0) & +S(3,1) \cdot (-x) & +S(3,2) \cdot (-x) \cdot (-x-1) & +S(3,3) \cdot (-x)(-x-1)(-x-2) \end{array}$$

Multiplying each summand of the already modified identity by $(-1)^{(n+1)}$ gets

$$\begin{array}{llll} a(3,0) & + a(3,1) \cdot x & + a(3,2) \cdot x \cdot (x+1) & + a(3,3) \cdot x \cdot (x+1) \cdot (x+2) \\ S(3,0) & +S(3,1) \cdot x & +S(3,2) \cdot x \cdot (x+1) & +S(3,3) \cdot x\cdot(x+1)\cdot(x+2) \end{array}$$

Is this correct? How do I put this altogether?

-
Have you tried fiddling with $x$ in the second identity to get it to look more like the first identity? – Qiaochu Yuan May 21 '11 at 18:37
What exactly do you mean by that? What should I do with the x? – muffel May 21 '11 at 18:53
What does it occur to you to do? Maybe you should write out both identities more explicitly, term-by-term, and see if something occurs to you. – Qiaochu Yuan May 21 '11 at 19:11
I modified the original post according to this – muffel May 21 '11 at 21:16
@muffel: You calculations contain errors and it is quite unclear how you arrive at your conclusion. – Phira May 22 '11 at 7:01

The shortest way to find the answer is to replace $x$ by $-x$ in one of the identities and then compare them.

-
Using this for the Stirling Numbers Identity I get for m = 3 S(3,0) + S(3,1)(-x) + S(3,2)(-x)(-1-x) + S(3,3)(-x)(-1-x)(-2-x) = a(3,0) + a(3,1) x + a(3,2) x (-1+x) + a(3,3) x (-1+x) (-2+x). Now the terms look more like each other, but the sign of x still differs. I don't see any way getting this switched.. Any further hint? – muffel May 22 '11 at 18:24
@muffel Collect the signs in front of each summand. – Phira May 22 '11 at 18:29
well, replacing x by (-x) and multiplying each summand by (-1) gets what I want. But the last part is still a mystery for me: What can I use to define a(m,n)? Just using "a(m,n) = S(m,n) * (-1)" won't change x to (-x) as no factor would at all. So what "trick" do I need here? – muffel May 22 '11 at 18:52
@muffel: You don't need a trick and $(-1)$ is not the right factor. Write it out in detail. – Phira May 22 '11 at 18:54
I added this to the original question. Why is (-1) not the right factor? $(-1)\cdot S(3,3)(-x)(-x-1)(-x-2)=S(3,3)\cdot x \cdot (x+1)(x+2)$ and this is what I want, or am I missing something? – muffel May 22 '11 at 19:23