Probably the most common formula for the power sum is the one involving binomial coefficients and Bernoulli numbers , sometimes called Faulhaber’s formula:
Historically, this, or a variant of it, was the first general formula for the power sum.
There are other ways to express the power sum, though. The subject of this post is to give a combinatorial proof for the following one involving Stirling numbers:
Proof: How many functions f are there from the set to the set such that for any ?
Answer 1: Condition on the value of . If , then there are k choices for , k choices for , etc., for a total of functions. Summing over all possible values of k gives the left side.
Answer 2: Condition on the number of elements in the range of f. (This is not the codomain, which is , but the subset consisting of elements from the codomain that have something from mapped to them. The range may be the entire codomain or a proper subset of it.) If the range of f has elements, there are ways to choose exactly which elements will comprise the range. The largest of these must be , and the remaining m elements in the domain must be mapped to the other k elements in the range. There are ways to assign the remaining m elements to k nonempty groups, and then k! ways to assign these groups to the actual k remaining elements in the range. (More generally, the number of onto functions from an m-set to a k-set is .) Summing over all possible values of k gives the right side.
(I first gave this proof as an answer here on Math.SE.)