The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial with non-negative integer coefficients and , let be the reciprocals of the roots of . Then

.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by . Today we’ll describe this species when is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.