A note on a recursion for the number of derangements
Using ideas in the recent paper of \textit{A. M. Garsia} and \textit{J. Remmel} [ibid. 1, 47--59 (1980; Zbl 0462.05012)] the author gives a direct bijective proof of the recursion \(D_{n+1}=(n+1)D_ n+(-1)^ n,\) where \(D_ n\) denotes the number of derangements of \(\{1,...,n\}\). Let \({\mathcal D}_ n\) denote the set of derangements of \(\{1,...,n\}\) (so that \(D_ n=| {\mathcal D}_ n|)\). Then the author proves that \[ {\mathcal D}_{2n}-\{\tau_{2n}\}\approx \{1,...,2n\}\times {\mathcal D}_{2n- 1} \] and \[ {\mathcal D}_{2n+1}\approx\{1,...,2n\}\times {\mathcal D}_{2n}\cup ({\mathcal D}_{2n}-\{\tau_{2n}\}) \] where \(A\approx B\) means that there is a bijection between \(A\) and \(B\), and where \[ \tau_{2n}=(12)(34)...(2n-1\, 2n). \]
scientific article; zbMATH DE number 3871369