Berkeley Math Circle

Solution:
The answer is the "superfactorial"
$$1! \cdot 2! \cdots n! = 1^{n} 2^{n-1} \cdots n^{1}$$
For $n=1$, the result is clear. We will prove as an induction step that there are $n!$ times as many happy polynomials of degree at most $n$ as of degree at most $n-1$.

Let $f(x)$ be a happy polynomial of degree at most $n$. We claim that the leading coefficient of $f$ is $c / n!$ for some integer $c$. One way to see this is using "Lagrange interpolation": let
$$f_{0}(x)=\sum_{0 \leq k \leq n}\left(f(k) \prod_{\substack{0 \leq j \leq n \\ j \neq k}} \frac{x-j}{k-j}\right)$$
On the one hand, $f_{0}(x)$ is clearly a polynomial of degree at most $n$ with rational coefficients. On the other hand, for each $x=0, \ldots, n$, we have $f_{0}(x)=f(x)$ since all terms for $k \neq x$ are zero and the remaining term is $f(x) \cdot 1$. Therefore $f_{0}=f$ since two distinct polynomials of degree $n$ can have at most $n$ common values. The leading coefficient of $f=f_{0}$ is a sum of terms of the form
$$\frac{1}{(-k)(-k+1) \cdots(-2)(-1) \cdot 1 \cdot 2 \cdots(n-k)} \cdot f(k)=\frac{ \pm 1}{k !(n-k) !} f(k)=\frac{ \pm\left(\begin{array}{l} n \\ k \end{array}\right)}{n !} f(k)$$
so it has the form $c / n!$ for $c \in \mathbb{Z}$.

By the given inequalities, we know that $0 \leq c < n!$. Given $f(x)$, let
$$g(x)=f(x)-c \cdot \frac{x(x-1) \cdots(x-n+1)}{n!},$$
a polynomial of degree at most $n-1$. For integers $x \geq n$, the fraction in the definition of $g(x)$ is the integer $\left(\begin{array}{l}x \\ n\end{array}\right)$, from which it is easy to see that $g(x)$ is an integer for all integers $x$. Let $h(x)$ be the polynomial obtained by reducing each coefficient of $g$ mod 1 so as to lie in the interval $[0,1)$. Then $f(x) \mapsto h(x)$ defines a bijection between
- happy polynomials of degree $\leq n$ with $n$th-degree coefficient $c / n!$, and
- happy polynomials of degree $\leq n-1$.

Since there are $n!$ possible values of $c$, it follows that there are $n!$ times as many happy polynomials of degree $\leq n$ as of degree $\leq n-1$.