A simple bijective proof of a familiar derangement recurrence

zbMATH Open1483.05003arXiv2005.11312MaRDI QIDQ4958083FDOQ4958083

Authors: Sergi Elizalde 

Publication date: 6 September 2021

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 $nge1$. Combinatorial proofs of this formula have been given by Remmel, Wilf, D'esarm'enien and Benjamin--Ornstein. Here we present yet another, arguably simpler, bijective proof.

Full work available at URL: https://arxiv.org/abs/2005.11312

Recommendations

• scientific article; zbMATH DE number 6985711
• A note on a recursion for the number of derangements
• On the combinatorics of derangements and related permutations
• The largest and the smallest fixed points of permutations
• A short combinatorial proof of derangement identity

zbMATH Keywords

bijective proofderangement numbers

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19)

Cited In (11)

• Recounting the Odds of an Even Derangement
• Bijectively deranging!
• A Bijection in the Theory of Derangements
• Bijective proofs of formulas with \((-1)^n\)
• A Simple Continuous Bijection from Natural Sequences to Dyadic Sequences
• Bijections for restricted inversion sequences and permutations with fixed points
• A classic proof of a recurrence for a very classical sequence
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the combinatorics of derangements and related permutations
• A note on a recursion for the number of derangements

This page was built for publication: A simple bijective proof of a familiar derangement recurrence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958083)