A simple bijective proof of a familiar derangement recurrence

Abstract

It is well known that the derangement numbers $d_n$, which count permutations of length $n$ with no fixed points, satisfy the recurrence $d_n=n{d}_{n-1}+(-1{)}^n$ for $n\ge 1$. Combinatorial proofs of this formula have been given by Remmel, Wilf, Désarménien and Benjamin--Ornstein. Here we present yet another, arguably simpler, bijective proof.

Cited by in corpus (1)

• Bijections for restricted inversion sequences and permutations with fixed points