Number of polynomials of degree less than 4 satisfying 5 points

By Lagrange interpolation, given the values of $P(1)$, $P(2)$, $P(3)$, $P(4)$, and $P(5)$, there is a unique polynomial of degree $\leq 4$ taking those values. So the question is, for which permutations of the numbers $1$ through $5$ will the resulting $P(x)$ actually have degree $<4$? To determine this, we can look at the actual explicit formula for Lagrange interpolation and see what the coefficient of $x^4$ will be in terms of our five values. That formula is $$\begin{align*}P(x)=P(1)\frac{(x-2)(x-3)(x-4)(x-5)}{(1-2)(1-3)(1-4)(1-5)}&+P(2)\frac{(x-1)(x-3)(x-4)(x-5)}{(2-1)(2-3)(2-4)(2-5)}\\ &+P(3)\frac{(x-1)(x-2)(x-4)(x-5)}{(3-1)(3-2)(3-4)(3-5)}\\ &+P(4)\frac{(x-1)(x-2)(x-3)(x-5)}{(4-1)(4-2)(4-3)(4-5)}\\ &+P(5)\frac{(x-1)(x-2)(x-3)(x-4)}{(5-1)(5-2)(5-3)(5-4)}, \end{align*}$$ so the coefficient of $x^4$ will be $$\frac{P(1)}{24}-\frac{P(2)}{6}+\frac{P(3)}{4}-\frac{P(4)}{6}+\frac{P(5)}{24}=\frac{P(1)-4P(2)+6P(3)-4P(4)+P(5)}{24}.$$ So we get a polynomial of degree $<4$ iff $$P(1)+6P(3)+P(5)=4(P(2)+P(4)).$$

Now we just have some casework to consider. If $P(3)=1$, the RHS will be at least $4(2+3)=20$ and the LHS is at most $5+6+4=15$, so there are no solutions. Since the problem is symmetric with respect to conjugating by $x\mapsto 6-x$, there are no solutions with $P(3)= 5$ either.

If $P(3)=2$, then $P(1)+P(5)$ is divisible by $4$, which means $P(1)$ and $P(5)$ must be $1$ and $3$ (in some order) or $3$ and $5$ (in some order). The equation will hold in the second case but not the first case. This gives four different solutions, since you can swap the two values of $P(1)$ and $P(5)$, and also the two values of $P(2)$ and $P(4)$. Again, by symmetry there are four more solutions if $P(3)=4$.

Finally, suppose $P(3)=3$. Then $P(1)+P(5)$ must be $2$ mod $4$, so $P(1)$ and $P(5)$ must be $1$ and $5$ (in some order) or $2$ and $4$ (in some order). Both cases work, and each gives four solutions. Thus there are eight solutions total if $P(3)=3$.

Taking all the cases together, then, we find there are sixteen different solutions.

Some closing remarks: It's not a coincidence that the coefficients of the values of $P$ in the equation we got are binomial coefficients; you can see this by noticing that the denominator in the Lagrange interpolation term with $P(n)$ is $\pm(n-1)!(5-n)!$ (grouping the positive and negative factors together), and this generalizes if you replace $5$ by another positive integer. Still, it would be nice to have a more conceptual explanation for why we're getting binomial coefficients. It would also be nice to have a more conceptual explanation for how to count the solutions (in particular, something that would generalize if you replaced $5$ by any positive integer).

Here is a computational approach:

Let $\pi \in \mathbb{R}^4$ represent the coefficients of a polynomial $p$ of degree $3$ or less. That is, $p(x) = \sum_{k=1}^4 p_k x^{k-1}$.

Define $A$ by $[A]_{ij} = i^{j-1}$, $[a]_j = 5^{j-1}$ for $i=1,...,4$ and $j=1,...,4$. Note that $A$ is invertible.

Let $(b,\beta)$ be a permutation of $\{1,...,5\}$ with $b \in \mathbb{R}^4$.

Then there is a polynomial whose values at $1,...,5$ are $(b,\beta)$ iff $A \pi = b, a^T \pi = \beta$, or equivalently, iff $a^T A^{-1} b = \beta$ iff $(a^T A^{-1},-1) (b, \beta)^T = 0$.

A quick computation shows that $(a^T A^{-1},-1) = (-1,4,-6,4,-1)$.

Grinding through the permutations gives $16$.

# python...
import itertools
total = 0
for x in itertools.permutations(xrange(1,6)):
    if 4*(x[1]+x[3])-(6*x[2]+x[0]+x[4]) == 0:
        total = total +1
print total

While Eric's case analysis is more thorough, we can cut the number of cases to consider down fairly quickly by looking at the vector $(-1,4,-6,4,-1)$.

Any permutation that swaps elements $1,5$ or $2,4$ will produce the same result, so we can assume $\pi_1< \pi_5$ and $\pi_2< \pi_4$ and multiply the resulting count by $4$.

If $(-1,4,-6,4,-1) \pi = 0$ then we see that $\pi_1+\pi_5$ must be even.

This shows that $\pi_1, \pi_5$ are restricted to $(1,3), (1,5), (2,4), (3,5)$, and since $\pi_2< \pi_4$, we have a total of $12$ cases to consider.

Clarification: As Eric (and the above computation, if you trust it) has shown the answer is 16. My comments above are just pointing out that if one was to do the problem by hand using the above technique, one would need to check 12 cases. After checking these, we would find that only 4 work, so the total number of cases is $4 \cdot 4 = 16$.

Eric's answer is more precise, mine is a lazier (from an intellectual standpoint) approach.

Well, given $n$ points, the only polynomial $P$ with $deg(P) < n$ that interpolates the points is the Lagrange Polynomial.

This means there's only one polynomial for each way of ordering $1,2,3,4,5$. In conclusion, there are $5!$ possible polynomials that interpolate the points. Most of the time, these polynomials will have degree $n-1$, so it will depend on the values interpolated. For a concrete case, you can compare each Lagrange Polynomial and see if the degree matches your requirement.