Let $g_{n}$ be the no. of derangements with $n$ elements and $f_{n}$ the no. of permutations with one fixed point. Show that $|g_{n}-f_{n}|=1$

Question

This is a problem from Loren Larson's "Problem solving through problems", 2.5.13, page 78.

Let $S_{n}=${$1,2,...,n$}. A derangement of $S_{n}$ is a permutation with no fixed points. Let $g_{n}$ be the number of derangements, and $f_{n}$ the number of permutations of $S_{n}$ with exactly one fixed point. Show that $|f_{n}-g_{n}|=1$

I proved that $g_{n}=(n-1)(g_{n-1}+g_{n-2})$, and by analyzing the number of permutations for $S_{3}$ and $S_{4}$ I've conjectured that $g_{2n}=f_{2n}+1$, and $g_{2n+1}=f_{2n+1}-1$, although I don't know how to prove it. I also found that $f_{n+1}=(n+1)g_{n}$.

Answer 1

HINT: Let $\pi$ be a permutation of $S_n$ with exactly one fixed point. Let $k$ be the fixed point; then $\pi\upharpoonright(S_n\setminus\{k\})$ is a derangement of $S_n\setminus\{k\}$. Let

$$s:S_n\setminus\{k\}\to S_{n-1}:\ell\mapsto\begin{cases} \ell,&\text{if }\ell<k\\ \ell-1,&\text{if }\ell>k\;; \end{cases}\tag{1}$$

$s$ is a bijection, and $s\circ\big(\pi\upharpoonright(S_n\setminus\{k\})\big)\circ s^{-1}$ is a derangement of $S_{n-1}$. Conversely, if $\pi$ is a derangement of $S_{n-1}$, $k\in S_n$, and $s$ is defined by $(1)$, then $s^{-1}\circ\pi\circ s$ is a permutation of $S_n$ having exactly one fixed point, $k$. Thus, $f_n=ng_{n-1}$. If you combine this with your recurrence for $g_n$, you should be able to finish the proof (and incidentally prove your observation about odd/even subscripts), but feel free to leave a question if you get stuck.

Answer 2

The generating function of derangements is $$\exp(-z) \frac{1}{1-z}.$$

This is because the species here is $$\mathfrak{P}(\mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \cdots)$$

which gives $$\exp\left(\frac{z^2}{2}+\frac{z^3}{3} +\frac{z^4}{4}+\cdots\right).$$

Hence we have for the number of derangements $$n! [z^n] \exp(-z) \frac{1}{1-z}$$

The generating function of permutations with fixed points marked is

$$\exp\left(uz - z +\log\frac{1}{1-z}\right)$$ which is $$\exp(uz-z)\frac{1}{1-z}$$

This is because the species here is $$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \cdots)$$

which gives $$\exp\left(uz + \frac{z^2}{2}+\frac{z^3}{3} +\frac{z^4}{4}+\cdots\right).$$

Hence we have for the number of permutations with one fixed point $$n! [z^n] [u] \exp(uz-z)\frac{1}{1-z}$$ which is $$n! [z^n] z \exp(-z)\frac{1}{1-z}.$$

The difference is $$n! [z^n] (1-z) \exp(-z) \frac{1}{1-z} = n! [z^n] \exp(-z) = (-1)^n,$$ thus proving the claim.

Answer 3

Let $D_n$ be the number of derangements in $S_n$. Obviously the number of permutations with exactly one fixed point is given by $n D_{n-1}$, so we just have to prove that for every $n$, $$ A_n = D_n-nD_{n-1}\in\{-1,1\}.$$ Let $\sigma$ be a derangement in $S_n$ and let $m=\sigma^{-1}(n)$. If we consider: $$ \tau = \sigma\, (n m) $$ i.e. the permutation we get by swapping the images of $n$ and $m$, we obviously have $\tau(n)=n$. Then, there are two cases: if $\tau(m)=m$, $\tau$ has exactly two fixed points, otherwise $n$ is the only fixed point. That leads (see also this question) to: $$ D_n = (n-1)\left(D_{n-1}+D_{n-2}\right) $$ that can be written as $A_n = -A_{n-1}$. Since $A_2=1$, the claim follows by induction.