Number of polynomials of degree less than 4 satisfying 5 points Let polynomial $P(x)$ have the property that $P(1),$ $P(2),$ $P(3),$ $P(4)$ and $P(5)$ are equal to $1$, $2$, $3$, $4$, $5$ in some order. How many possibilities are there for the polynomial $P,$ given that the degree of $P$ is strictly less than $4$?

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).
