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
    @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
    @mu$f$fel: You are welcome.2011-05-23