Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 2 down vote accepted

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

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

Your Answer


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.