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