6
$\begingroup$

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?

$\endgroup$
9
  • $\begingroup$ Have you tried fiddling with $x$ in the second identity to get it to look more like the first identity? $\endgroup$
    – Qiaochu Yuan
    May 21, 2011 at 18:37
  • $\begingroup$ What exactly do you mean by that? What should I do with the x? $\endgroup$
    – muffel
    May 21, 2011 at 18:53
  • $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    May 21, 2011 at 19:11
  • $\begingroup$ I modified the original post according to this $\endgroup$
    – muffel
    May 21, 2011 at 21:16
  • $\begingroup$ @muffel: You calculations contain errors and it is quite unclear how you arrive at your conclusion. $\endgroup$
    – Phira
    May 22, 2011 at 7:01

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – muffel
    May 22, 2011 at 18:24
  • $\begingroup$ @muffel Collect the signs in front of each summand. $\endgroup$
    – Phira
    May 22, 2011 at 18:29
  • $\begingroup$ 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? $\endgroup$
    – muffel
    May 22, 2011 at 18:52
  • $\begingroup$ @muffel: You don't need a trick and $(-1)$ is not the right factor. Write it out in detail. $\endgroup$
    – Phira
    May 22, 2011 at 18:54
  • $\begingroup$ 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? $\endgroup$
    – muffel
    May 22, 2011 at 19:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .