wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> An identity with stirling numbers
        
(Message started by: Aryabhatta on Jul 9^th, 2009, 10:49am)

Title: An identity with stirling numbers
Post by Aryabhatta on Jul 9^th, 2009, 10:49am

If S(n,k) is a stirling number of second kind, prove/disprove that

Sum {k = 0 to n} (-1)^k * k! * S(n,k) = (-1)ⁿ

Stirling number of second kind:
http://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind

S(n,k) is basically the number of ways to partition an n element set into k non-empty subsets.

Title: Re: An identity with stirling numbers
Post by Eigenray on Jul 9^th, 2009, 2:56pm

[hide]Sum {k = 0 to n} (-1)^k * s(n,k) = (-1)ⁿ * n![/hide] ;)

Title: Re: An identity with stirling numbers
Post by Obob on Jul 9^th, 2009, 3:10pm

Don't you just plug x = -1 into the generating function on the wikipedia page?

Title: Re: An identity with stirling numbers
Post by Aryabhatta on Jul 9^th, 2009, 3:44pm

on 07/09/09 at 15:10:37, Obob wrote:

Don't you just plug x = -1 into the generating function on the wikipedia page?

Err, yes... I only intended it as a reference to the definition and maybe some insight. If you use something there, maybe you should prove it too :P

Title: Re: An identity with stirling numbers
Post by Aryabhatta on Jul 9^th, 2009, 3:45pm

on 07/09/09 at 14:56:39, Eigenray wrote:

[hide]Sum {k = 0 to n} (-1)^k * s(n,k) = (-1)ⁿ * n![/hide] ;)

[EDIT]~~I don't understand...~~[/EDIT]

Ahh... Now I do! You have s(n,k), not S(n,k).

Title: Re: An identity with stirling numbers
Post by Eigenray on Jul 11^th, 2009, 7:35pm

http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S(n,k) (x)_k = xⁿ
The number of surjective functions f : N http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif K is S(n,k) k!, since we can partition N by which elements map to 1,2,..,k. So the number of functions f : N http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/to.gif X with an image of size k is S(n,k) k! C(x,k) = S(n,k) (x)_k. Summing over all k, we get all xⁿ functions. Now just let x = -1 in the above argument ;)

What I was hinting at before is to consider the Stirling numbers of the first kind, s(n,k) = (-1)^n-k c(n,k), where c(n,k) is the number of n-element permutations with k cycles. These numbers satisfy the inverse relationship:
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif s(n,k) x^k = (x)_n.
This means that (s(i,j)) and (S(i,j)) are precisely the matrices to change between the bases {xⁿ} and {(x)_n} of the space of polynomials, and are therefore inverses of each other.
So
http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif S(n,k) (-1)^k k! = (-1)ⁿ
is equivalent to
(-1)^k k! = http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif s(k,n) (-1)ⁿ,
which is obvious.

Title: Re: An identity with stirling numbers
Post by zahari20 on Sep 21^st, 2009, 8:09pm

Hello!
This result is included in the paper (free)
A series transformation formula and related polynomials

http://www.hindawi.com/journals/ijmms/2005/792107.cta.html