A polynomial $f(x)=\sum_{i=0}^{n} a_{i} x^{i}$ of degree $n$ or less is called happy if

(i) Each coefficient $a_{i}$ satisfies $0 \leq a_{i}<1$;

(ii) $f(x)$ is an integer for all integers $x$.

Find the number of happy polynomials of degree $n$ or less.
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$.