Author |
Topic: An identity with stirling numbers (Read 1193 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
An identity with stirling numbers
« on: Jul 9th, 2009, 10:49am » |
 Quote  Modify
|
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)n
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.
|
|
 IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: An identity with stirling numbers
« Reply #1 on: Jul 9th, 2009, 2:56pm » |
Quote Modify
|
Sum {k = 0 to n} (-1)k * s(n,k) = (-1)n * n! 
|
|
IP Logged |
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: An identity with stirling numbers
« Reply #2 on: Jul 9th, 2009, 3:10pm » |
Quote Modify
|
Don't you just plug x = -1 into the generating function on the wikipedia page?
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: An identity with stirling numbers
« Reply #3 on: Jul 9th, 2009, 3:44pm » |
Quote Modify
|
on Jul 9th, 2009, 3:10pm, 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 
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: An identity with stirling numbers
« Reply #4 on: Jul 9th, 2009, 3:45pm » |
Quote Modify
|
on Jul 9th, 2009, 2:56pm, Eigenray wrote:| Sum {k = 0 to n} (-1)k * s(n,k) = (-1)n * n! |
|
[EDIT]I don't understand...[/EDIT]
Ahh... Now I do! You have s(n,k), not S(n,k).
|
| « Last Edit: Jul 9th, 2009, 5:28pm by Aryabhatta » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: An identity with stirling numbers
« Reply #5 on: Jul 11th, 2009, 7:35pm » |
Quote Modify
|
 S(n,k) (x)k = xn
The number of surjective functions f : N  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 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 xn 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:
s(n,k) xk = (x)n.
This means that (s(i,j)) and (S(i,j)) are precisely the matrices to change between the bases {xn} and {(x)n} of the space of polynomials, and are therefore inverses of each other.
So
S(n,k) (-1)k k! = (-1)n
is equivalent to
(-1)k k! = s(k,n) (-1)n,
which is obvious.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print