A simple bijective proof of a familiar derangement recurrence

MaRDI QIDQ4958083zbMATHFDO

Authors Sergi Elizalde

Publication date 6 September 2021

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

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

(11)

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

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)