Generating function of the number of permutations of length n with exactly k fixed points

combinatoricsgenerating-functionspermutations

Let $p_{n}(k)$ denote the number of permutations of length $n$ with exactly $k$ fixed points (a fixed point of $\pi$ is an element $t$ such that $\pi(t)=t$ ). Show that the generating function
$$
f_{n}(x)=\sum_{i=0}^{n} x^{i} p_{n}(i)
$$

satisfies $f_{n}(1)=f_{n}^{\prime}(1)=n !$

EDIT:
Question context: Math graduate course – Probabilistic methods (2020)
My work: since every permutation of length n has a number of fixed points between 0 and n included it implies that $f_{n}(1)=n !$

Best Answer

Note that the number of permutations of length $n$ with exactly $k$ fixed points is $\binom{n}{k}\mathcal{D}(n-k)$ because there are $\binom{n}{k}$ ways to choose the fixed points and $\mathcal{D}(n-k)$ to arrange the others, where $\mathcal{D}(k)$ is the number of Derangements of $k$ items.

Therefore, the generating function is $$ \begin{align} \overbrace{\sum_{k=0}^n\binom{n}{k}\mathcal{D}(n-k)x^k}^{f_n(x)} &=\sum_{k=0}^n\overbrace{\frac{n!}{k!(n-k)!}\vphantom{\sum_0^k}}^{\binom{n}{k}}\overbrace{\sum_{j=0}^{n-k}(-1)^j\frac{(n-k)!}{j!}}^{\mathcal{D}(n-k)}x^k\tag{1a}\\[6pt] &=n!\!\!\sum_{\substack{j,k\ge0\\j+k\le n}}\!\!\frac{(-1)^j}{j!\,k!}x^k\tag{1b}\\ &=n!\sum_{m=0}^n\sum_{j=0}^m\frac{(-1)^j}{j!\,(m-j)!}x^{m-j}\tag{1c}\\[3pt] &=n!\sum_{m=0}^n\frac1{m!}\sum_{j=0}^m\binom{m}{j}x^{m-j}(-1)^j\tag{1d}\\[3pt] &=\sum_{m=0}^n\frac{n!}{m!}(x-1)^m\tag{1e} \end{align} $$ Explanation:
$\text{(1a)}$: expand $\mathcal{D}(n-k)$ (from $(5)$ in this answer) and $\binom{n}{k}$
$\text{(1b)}$: cancel terms and reindex
$\text{(1c)}$: substitute $m=j+k$
$\text{(1d)}$: multiply and divide by $m!$
$\text{(1e)}$: apply the Binomial Theorem

Thus, for $0\le m\le n$, $$ f^{(m)}(1)=n!\tag2 $$