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

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 !$$

• Have you got any thoughts of your own on this? Hint: $p_n(0)+p_n(1)$ is the number of permutations in $S_n$ with zero or with one fixed point. What can you say about $p_n(0)+p_n(1)+p_n(2)+\dots+p_n(n)$? How many fixed points are possible for permutations in $S_n$? Aug 3, 2021 at 21:26
• Well I understand that the hint solves the first question, because every permutation of length n has a number of fixed points between 0 and n included. For the second part about the derivative I am not sure. After calculating I get $f_{n}^{\prime}(1)= \sum_{i=0}^{n} i p_{n}(i)$ but nothing after this. Aug 3, 2021 at 21:37
• 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.
– robjohn
Aug 4, 2021 at 7:08
• Context added following the guidelines. Aug 4, 2021 at 19:01

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$$

Consider permutations of $$[n]$$: Each permuatution will have $$i$$ fixed points (where $$i$$ ranges from $$0$$ to $$n$$) & for a given value $$i$$, $$p_n(i)$$ of them will have $$i$$ fixed points, so $$\begin{eqnarray*} p_n(0)+p_n(1) +\cdots+p(_n(n)=n! \end{eqnarray*}$$ and thus $$f_{n}(1)=n !$$.

To show the second part we need to notice that $$ip_n(i)=np_{n-1}(i-1)$$. This can be shown by the following combinatorial arguement: Given a permuatation of $$[n]$$ with $$i$$ fixed points, choose one of these fixed points. Now delete this element and reorder the other larger elements by decreasing them by $$1$$ to give a permutation of $$n-1$$ with $$i-1$$ fixed points & each of these permutations can be obtained in $$n$$ possible ways.