This post isn't really about Newton polynomials

First, we will need the following

Proposition: Let be two sequences with exponential generating functions and suppose that . Then



Exponential generating functions are used to study sequences like the Bell numbers whose growth rate makes their ordinary generating functions bad (for example, they might converge nowhere). The multiplication of exponential generating functions, as opposed to ordinary generating functions, occurs in situations where order counts. Certainly there's much more to be said about this point.

But the interesting thing here is the correspondence between the convolution above and an operation I referred to as a "Newton transform" (this is not standard terminology) that assigns to a sequence the function



If we shift our focus of attention instead to the sequence



we can find in it a combinatorial interpretation: if is the number of ways to arrange objects in some way such that order matters, is the number of ways to arrange some objects from among distinguishable objects in that way. It is now obvious that



This is poweful! If is a polynomial, it consists of a finite number of terms whose coefficients specify the coefficients, in Newton form, of a polynomial whose positive integer values are the coefficients of the LHS! It appears that multiplication by alone is enough for us to automatically compute values of a polynomial by specifying only its Newton coefficients. You may also recall a combinatorial identity whose (non-combinatorial!) proof is now trivial: letting gives



hence and



as before. Also note that the combinatorial interpretation of I gave above is consistent with the interpretation I gave in that post.

Earlier I noted another special case when was a geometric series, which gives and



exactly as shown earlier. Now let's talk about the roots of unity filter again: this corresponds to the case where

.

For example, if , the corresponding generating function is . The product will then tell us how to evaluate the sum

.

By inspection, is a solution to the differential equation , so it is a linear combination of functions of the form where and . This is all material we have more or less encountered already. An application of the DFT gives us




.

When , this gives



as before. Now, these generating functions are a little unwieldy (complex numbers as an argument in an exponent?), so we might like to see what ordinary generating functions have to say about all of this. But what happens to the exponential convolution? We could use the properties of the Laplace transform, but let's work backwards instead: we want to find a relationship between the generating functions



and



Exchanging the order of summation in , we obtain



We've seen a generating function very much like this one before; it gives



and therefore

.

This is either very nice or very ugly depending on your point of view; in any case, it agrees with the answer you get using the properties of the Laplace transform (). We're interested in the function , which gives



The factorization of the denominator into linear terms of the form gives as before, which is very nice, but to find the coefficients we found before requires a partial fraction decomposition, either of or of . We can compute the partial fraction decomposition of using the DFT as before - which is already a nice result - but we can be tricky: observe that if we write



then we can compute the residue by computing



l'Hospital's rule then gives



which is in exact agreement with our previous answer, although we need to rewrite the partial fraction decomposition as



to see the agreement. This can be understood as an alternate proof that the DFT works; the proof sketched in a previous post was about orthogonality and can be understood in the context of Parseval's theorem.

---

So it seems that both ordinary and exponential generating functions have something to bring to the table. Exponential generating functions reveal that a convolution with is what makes the "Newton transform" work (see binomial transform), but there were difficulties - we could not explicitly write down in terms of a well-known function. The convolution became a Mobius transformation of the ordinary generating function, but there we had partial fractions and analysis available.

---

Practice Problem 1: Repeat the above computation using the formula

.

Practice Problem 2: Show that cannot be partitioned into a finite number of disjoint arithmetic sequences with each common difference distinct.

Practice Problem 3: The Bell numbers count the number of partitions of a set with elements, where neither the order of the partitions nor the order of the elements of a partition matter. Show that they satisfy the recurrence

.

Hence compute the exponential generating function .