A note on a recursion for the number of derangements
type: Item
instance of: scholarly article
title: A note on a recursion for the number of derangements
zbMATH Open document ID: 0547.05007
DOI: 10.1016/S0195-6698(83)80034-1
published in: European Journal of Combinatorics
publication date: 1983-01-01T00:00:00Z
review text: 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). \]
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A05
zbMATH DE Number: 3871369
zbMATH Keywords: permutations
zbMATH Keywords: derangements
zbMATH Keywords: bijective proof
author: Jeffrey Remmel
MaRDI profile type: Publication
cites work: A combinatorial interpretation of q-derangement and q-Laguerre numbers
full work available at URL: s0195-6698(83)80034-1
OpenAlex ID: W2058395674
description: scientific article; zbMATH DE number 3871369