math154 wrote: Let $Q(x)$ be a polynomial with integer coefficients. Prove that there exists a polynomial $P(x)$ with integer coefficients such that for every integer $n\ge\deg{Q}$, \[\sum_{i=0}^{n}\frac{!i P(i)}{i!(n-1)!} = Q(n),\]where $!i$ denotes the number of derangements (permutations with no fixed points) of $1,2,\ldots,i$. Calvin Deng. There is something wrong in this statement. Take $Q(x) \equiv 1$. Then there should exist a polynomial $P(x)$ of some degree $k$, such that for every integer $n \geq 0$: $ \sum_{i=0}^{n}\frac{!i P(i)}{i!}= (n-1)! $. Hence: $\frac{!(n+1) P(n+1)}{(n+1)!} = n!-(n-1)!=(n-1)(n-1)!$. Notice that the growth of LHS is $O(n^k)$, while the growth of RHS can not be of polynomial rate.

Yes, it is OK now. Nice problem! It is known that: (1) $! i = i! \sum_{j=0}^i (-1)^j \frac{1}{j!}$. Let $P(x)$ is some polynomial. Using (1) we get. $ \sum_{i=0}^{n}\frac{!i P(i)}{i!(n-i)!}= \sum_{i=0}^n \sum_{j=0}^i \frac{(-1)^j P(i)}{j! (n-i)!} = $ $= \sum_{j+k \leq n} \frac{(-1)^j P(n-k)}{j! k!} = \sum_{\ell=0}^{n} \frac{1}{\ell !} \sum_{j+k=\ell} (-1)^{l-k} \binom{\ell}{k} P(n-k)= $ (2) $= \sum_{\ell=0}^{n} \frac{1}{\ell !} \Delta_{-1}^{\ell} P(n)$. where $\Delta_{h}^{\ell} P(x)$ is the $\ell$-th finite difference with step $h$. (2) resembles Newton's interpolation formula. Notice that $\Delta_{-1}^{\ell} P(n) = 0$, when $\ell > r = \deg P$, so in (2) it is enough to sum from 0 to $r$. Let define an operator $L: \mathbb{Z}[x] \to \mathbb{Q}[x]$. Assume $P(x)$ is a polynomila with integer coefficients. Then define: (3) $ L(P)(x)= \sum_{\ell=0}^{\deg P} \frac{1}{\ell !} \Delta_{-1}^{\ell} P(x) $. Because $L$ is a linear operator it will be enough to find polinomials with integer coefficients $P_1,P_2,\ldots$ such that $L(P_i) = x^i$, In order to do this let plug into (3) the polynomial $(x)_r = x(x-1)\ldots (x-r+1)$. First notice that: $\Delta^{\ell}_{-1} (x)_r = \Delta^{\ell-1}_{-1} \Delta_{-1}(x)_r= \Delta^{\ell-1}_{-1} \left( (x-1)_r - (x)_r\right)= -r \Delta^{\ell-1}_{-1} (x-1)_{r-1}$. Therefore $\Delta^{\ell}_{-1} (x)_r = (-1)^{\ell}\frac{r(r-1)\ldots (r-l+1)}{\ell!} (x-\ell)_{r-l} $ . Hence: $L\left((x)_r\right) = (x)_r + a_1 (x-1)_{r-1}+\ldots + a_{r-1}(x-r+1) + a_r $, where $a_i$ are integers. $\Rightarrow$ (4) $(x)_r = L\left((x)_r\right) - a_1 (x-1)_{r-1}-\ldots - a_{r-1}(x-r+1) - a_r $ . Using (4) we can prove by induction that there exist polynomials with integer coefficients $P_1,P_2,\ldots,P_{r+1}$ so that: $(x)_r = \sum_{i=1}^{r+1} L(P_i)$. Finally it remains to notice that $x,x^2,x^3,\ldots$ can be represent as linear combinations with integer coefficients of $x, (x)_2, (x)_3,\ldots$ and theirs translations by some integer.

Let us call $P_0(x)=1$, $P_1(x)=x, P_2(x)=x(x-1),\cdots P_k(x)=x(x-1)\cdots (x-k+1),\cdots$. Now, we claim that for $Q(x)=x^k$, $P$ works as a linear combination of $P_0(x), P_1(x), \cdots P_k(x)$. We will proceed by induction. For $k=0$, observe that \[\sum_{i=0}^{n}\frac{!i}{i!(n-i)!}=\frac{1}{n!}\sum \binom{n}{i}!i \]but $\binom{n}{i}!i$ is the number of permutations with $n-i$ fixed points. Thus, we get that $\frac{1}{n!}\sum \binom{n}{i}!i =\frac{n!}{n!}=1$. Now, we proceed by induction, assume that we have proved our result up to $k-1$. Now, let $S_i$ be the number of $i+1$ tuples of the form $(\sigma, a_1, a_2, \cdots a_{i})$ where $\sigma$ is a permutation with at most $n-i$ fixed points of $[n]$ and $a_1,\cdots a_{i-1}, a_i$ are non-fixed points in $\sigma$. We now double count $S_k$, observe that we have $S_k=\sum \binom{n}{i}!i P_k(n)$. But, we can also count $S_k=(n(n-1)\cdots (n-k+1))((n!-k(n-1)!+\cdots (-1)^j(n-j)!))$ by inclusion exclusion principle as we first pick the $k$ non-fixed points in order. Thus, we get $\frac{1}{n!}\sum \binom{n}{i}!i P_k(x)=\frac{1}{(n-k)!}(n!-k(n-1)!+\cdots (-1)^j\binom{k}{j}(n-j)!+\cdots+(-1)^k(n-k)!)$. Observe that this is a polynomial in $n$ with integer coefficients and degree $k$ with leading coefficient $1$. Now, as $x^{k-1},\cdots 1$ can all be written as a linear combination of $P_0(x),\cdots P_{k-1}(x)$, we can write $\frac{1}{n!}\sum \binom{n}{i}!i (P_k(x)+R(n))=n^k$ where $R(n)$ can be written as a linear combination of $P_0(n),\cdots P_{k-1}(n)$. Thus, $n^k$ can be written using a linear combination of $P_0(n),\cdots P_k(n)$ as $P$ Now, we can write $Q(x)$ using a linear combination of $P_0(x),P_1(x),P_2(x),\cdots P_{\deg Q}(x)$ as $P$ and we are done!

We will consider polynomials of the form $Q_k(n-k)=\frac{1}{n!} \sum\limits_{t=0}^n \binom nt !t \left(\binom tk \cdot k! \right)$. I will prove that this is a monic polynomial with integral coefficients and degree $k$. This is equivalent to $\frac{1}{(n-k)!} \sum\limits_{t=0}^n \binom{n-k}{t-k} !t = Q_k(n-k)$ Base case: When $k=0$, $\frac{1}{n!} \sum\limits_{t=0}^n \binom nt !t=1$ because we can double count the number of permutations of $n$ elements. On one hand, this number is $n!$. On the other hand, count the number of permutations with $n-t$ fixed points. There are $\binom nt$ ways to fix the $n-t$ fixed points and the $t$ other elements form a derangement. Therefore, $n!= \sum\limits_{t=0}^n \binom nt !t$ so $Q_0(n)=1$ Inductive Step: $Q_k(n)=\frac{1}{n!} \sum\limits_{t=0}^n \binom{n}{t} !(t+k) = \frac{1}{n!} \sum\limits_{t=0}^n \left( \binom{n+1}{t+1}-\binom{n}{t+1} \right) !(t+k) = \frac{1}{(n+1)!} (n+1) \sum\limits_{t=0}^{n+1} \binom{n+1}{t} !(t+k-1) - \frac{1}{n!}\sum\limits_{t=0}^{n}\binom{n}{t} !(t+k-1)$ $=(n+1)Q_{k-1}(n+1)-Q_{k-1}(n)$, which has integer coefficients and is monic. Therefore, $Q_k(n-k)=\sum_{i=0}^{n}\frac{!i \binom{i}{k}k! }{i!(n-i)!}$ forms a basis over $\mathbb{Z}[x]$. Since $\binom{i}{k}k!$ is a polynomial with integer coefficients, the conclusion follows.