A simple bijective proof of a familiar derangement recurrence

MaRDI QIDQ4958083zbMATH OpenFDO

Authors Sergi Elizalde

Publication date 6 September 2021

Full work available at URL https://arxiv.org/abs/2005.11312, https://www.fq.math.ca/Abstracts/59-2/elizalde.pdf

zbMATH Keywords

bijective proofderangement numbers

Mathematics Subject Classification ID

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

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.

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

Cited in

(13)

• The skew, relative, and classical derangements
• Another interpretation of the number of derangements
• A classic proof of a recurrence for a very classical sequence
• Bijectively deranging!
• On the combinatorics of derangements and related permutations
• A Simple Continuous Bijection from Natural Sequences to Dyadic Sequences
• A Bijection in the Theory of Derangements
• Recounting the Odds of an Even Derangement
• scientific article; zbMATH DE number 5014508 (Why is no real title available?)
• scientific article; zbMATH DE number 6985711 (Why is no real title available?)
• Bijections for restricted inversion sequences and permutations with fixed points
• Bijective proofs of formulas with (-1)^n
• 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)