Re: Combinatorial question

In news:<eorh9g$iek$1@xxxxxxxxxxxxxxxxxxxxxx>
schrieb Robert Israel <israel@xxxxxxxxxxx>:
José Carlos Santos <jcsantos@xxxxxxxx> wrote:

Someone posted this question at a french mathematical newsgroup: is
it true that, if _p_ and _N_ are natural numbers, then

(-1)^p C(p,1) + (-1)^{p - 1}C(p,2)2^N + (-1)^{p - 2}C(p,3)3^N + ...

... + C(p,p - 1)(p - 1)^N = p^N,

where C(p,k) = p!/(k!(p - k)!)? Someone else replied that, if _p_ and
_N_ are both equal to 3, then the term on the left is -3 + 24 = 21,
whereas the term on the right is 3^3 = 27.
[ ... ]
Is the equality always true when p > N? Can someone provide a proof?

In other words, you want

sum_{k=0}^p (-1)^k C(p,k) k^N = 0 for p > N

For fixed positive integer p, let
A(N) = sum_{k=0}^p (-1)^k C(p,k) k^N

Consider the exponential generating function
g(t) = sum_{N=0}^infty A(N) t^N/N!
= sum_{k=0}^p (-1)^k C(p,k) exp(kt)
= (1 - exp(t))^p
[ ... ]

Fits in well with my previous answer:
Notice that (exp(t) - 1) is the exponential generating function
for the number of ways to partition a set of N elements
into _one_ _non-empty_ subset. ;-)

Hence, (exp(t) - 1)^p will be the exponential generating function
for the number of ways to partition a set of N elements
into p non-empty subsets with labels 1 to p,
or, in other words, the number of surjective maps
from {1,2,...,p} onto a set of N elements.

Thus, the entries (-1)^p * A(N) / p!
are the Stirling numbers of second kind.
(In particular, each A(N) is divisible by p!)
.