5
$\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?

  • 0
    Have you tried fiddling with $x$ in the second identity to get it to look more like the first identity?2011-05-21
  • 0
    What exactly do you mean by that? What should I do with the *x*?2011-05-21
  • 0
    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.2011-05-21
  • 0
    I modified the original post according to this2011-05-21
  • 0
    @muffel: You calculations contain errors and it is quite unclear how you arrive at your conclusion.2011-05-22
  • 0
    You've got the case $m=1$ wrong to start with. What you should have is $\Sigma_{n=0}^m a(m,n) x^{\overline{n}} = \Sigma_{n=0}^m S(m,n) x^{\underline{n}}$2011-05-22
  • 0
    @user9325 This was just what I expected. I arrived at my conclusion by putting the terms containing "S(m,n)" just below the ones containing the "a(m,n)" ones. After doing that I saw that (except from the first term which is always 0) both terms look the same. Could you please tell me what my errors are?2011-05-22
  • 0
    Please check the case $m=1$ first. You *should* try to find your errors to practice, but the problem I see that you decided that "terms look the same" that are not the same. But for solving the actual question, I propose that you start by rewriting your general equation in a way that both sides use the product symbol or neither side uses it.2011-05-22
  • 0
    @user9325 OK, I found (hopefully all of) them and corrected the question.2011-05-22

1 Answers 1

2

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

  • 0
    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?2011-05-22
  • 0
    @muffel Collect the signs in front of each summand.2011-05-22
  • 0
    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?2011-05-22
  • 0
    @muffel: You don't need a trick and $(-1)$ is not the right factor. Write it out in detail.2011-05-22
  • 0
    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?2011-05-22
  • 0
    This is just one case, not the general case.2011-05-22
  • 0
    Of course, you were right. It's $(-1)^{(n+1)}$ which I have to multiply all summands with. But I still have the problem that I replaced x by (-x). So setting "a(n,m) = (-1)^{(n+1)}$" is not enough. How do I add the part concerning the "-x"?2011-05-22
  • 0
    @muffel: What happens to the other side of the equation when you replace $x$ by $-x$?2011-05-22
  • 0
    ok, what about $a(m,n) = S(m,n) \cdot (-1)^{(n+m)}$? this should cover both, the inverted x and the conversion by (-1).2011-05-23
  • 0
    @muffel: Yes, this is correct.2011-05-23
  • 0
    great, thank you very much for your help and patience!2011-05-23
  • 0
    @muffel: You are welcome.2011-05-23