Philippe Duchon ; Romaric Duvignau - A new generation tree for permutations, preserving the number of fixed points

dmtcs:2433 - Discrete Mathematics & Theoretical Computer Science, January 1, 2014, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) - https://doi.org/10.46298/dmtcs.2433
A new generation tree for permutations, preserving the number of fixed pointsArticle

Authors: Philippe Duchon 1; Romaric Duvignau ORCID1

  • 1 Laboratoire Bordelais de Recherche en Informatique

We describe a new uniform generation tree for permutations with the specific property that, for most permutations, all of their descendants in the generation tree have the same number of fixed points. Our tree is optimal for the number of permutations having this property. We then use this tree to describe a new random generation algorithm for derangements, using an expected n+O(1) calls to a random number generator. Another application is a combinatorial algorithm for exact sampling from the Poisson distribution with parameter 1.


Volume: DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
Section: Proceedings
Published on: January 1, 2014
Imported on: November 21, 2016
Keywords: generation tree,fixed points,permutations,random generation,derangements,[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 196 times.
This article's PDF has been downloaded 194 times.