Combinatorial Polynomials
-------------------------
Consider C(n,k) as a degree k polynomial in n, the combinatorial
polynomial of degree k.  That is,

    C(n,k) = n(n-1)(n-2)(n-3)...(n-k+1)/k!

Integral Injective Polynomials
------------------------------
Because C(n,k) is an integer whenever n is, it is easy to see that any
integral linear combination of combinatorial polynomials maps integers
to integers.  However, the converse is also true: if a polynomial maps
integers to integers, then it is an integral linear combination of
combinatorial polynomials.

Let L_k be the set of integral linear combinations of combinatorial
polynomials of degree at most k.

Claim: Let { a_j | j = 0...k } be a set of k+1 integers, then there
exists a P in L_k such that P(j) = a_j for j = 0...k.

Proof by induction: since C(n,0) = 1, the claim is trivial for k = 0.

Suppose the claim is true for some k and let { a_j | j = 0...k+1 } be a
set of k+2 integers.  Let Q be an element of L_k so that Q(j) = a_j for
j from 0 to k.  Then b = a_{k+1} - Q(k+1) is an integer.  Since C(j,k+1)
is 0 for j from 0 to k and C(k+1,k+1) = 1, P(j) = Q(j) + b C(j,k+1) is
an element of L_{k+1}, P(j) = Q(j) = a_j for j from 0 to k, and P(k+1)
is Q(k+1) + b C(k+1,k+1) = Q(k+1) + (a_{k+1} - Q(k+1)) = a_{k+1}.  Thus,
the claim is true for k+1.

Let Q be a polynomial of degree k that maps integers to integers.  Let P
be a polynomial in L_k such that P(j) = Q(j) for j from 0 to k.  Since
a polynomial of degree k is determined by its values at k+1 points, we
must have that P = Q; that is, Q is in L_k.

We have shown that a polynomial maps integers to integers if and only if
it is an integral linear combination of combinatorial polynomials.

Representing Monomials
----------------------
The previous section implies that any monomial x^k can be written as an
integral linear combination of combinatorial polynomials.  Let us look
for a recursion that gives the coefficients of this integral linear
combination.

First, let us start with a simple combinatoric identity:

    (n-k) C(n,k) = (k+1) C(n,k+1)                            [1]

adding k C(n,k) to both sides, we get

    n C(n,k) = (k+1) C(n,k+1) + k C(n,k)                     [2]

Now, suppose we have a(k,j) so that

     k   ---
    n  = >   a(k,j) C(n,j)
         ---

Multiplying both sides by n gives

     k+1   ---
    n    = >   a(k,j) n C(n,j)
           ---

           ---
         = >   a(k,j) [(j+1) C(n,j+1) + j C(n,j)]
           ---

           ---                     ---
         = >   a(k,j-1) j C(n,j) + >   a(k,j) j C(n,j)
           ---                     ---

           ---
         = >   [a(k,j-1) + a(k,j)] j C(n,j)                  [3]
           ---

Equation [3] gives us the recursion we were looking for

    a(k+1,j) = [a(k,j-1) + a(k,j)] j                         [4]

Since 1 = C(n,0), we have that a(0,0) = 1 and a(0,j) = 0 for j <> 0.
From this and [4] we get the following table for a(k,j):

    k\j    0       1       2       3       4       5
    ----------------------------------------------------
    0      1       0       0       0       0       0
    1      0       1       0       0       0       0
    2      0       1       2       0       0       0
    3      0       1       6       6       0       0
    4      0       1      14      36      24       0
    5      0       1      30     150     240     120

For example, n^3 = 6 C(n,3) + 6 C(n,2) + C(n,1).

It is apparent from the table that the highest order term for n^k is
k! C(n,k).  We can show this directly using recurrence [4].

Claim: a(k,j) = 0 when j > k.

Proof: induction on k.  This is true for k = 0 because we noted above
that a(0,j) = 0 for j <> 0.

Suppose that the statement is true for some k and that j > k+1.  Then
[4] says that a(k+1,j) = 0 since both a(k,j-1) = 0 and a(k,j) = 0.
Thus, the claim is true for k+1.

Claim: a(k,k) = k!

Proof: induction on k.  This is true for k = 0 because we noted above
that a(0,0) = 1.

Suppose that the statement is true for some k, then using [4] we get

    a(k+1,k+1) = [a(k,k) + a(k,k+1)] (k+1)

               = [ k! + 0 ] (k+1)

               = (k+1)!

Thus, the claim is true for k+1.

Rob Johnson