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.)