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