A new generation tree for permutations, preserving the number of fixed points
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 d...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2014-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/2433/pdf |
| _version_ | 1797270322665226240 |
|---|---|
| author | Philippe Duchon Romaric Duvignau |
| author_facet | Philippe Duchon Romaric Duvignau |
| author_sort | Philippe Duchon |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T02:02:26Z |
| format | Article |
| id | doaj.art-fa4018537a1940f893920580f2be55f7 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:02:26Z |
| publishDate | 2014-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-fa4018537a1940f893920580f2be55f72024-03-07T14:53:18ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502014-01-01DMTCS Proceedings vol. AT,...Proceedings10.46298/dmtcs.24332433A new generation tree for permutations, preserving the number of fixed pointsPhilippe Duchon0Romaric Duvignau1https://orcid.org/0000-0003-1268-9311Laboratoire Bordelais de Recherche en InformatiqueLaboratoire Bordelais de Recherche en InformatiqueWe 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.https://dmtcs.episciences.org/2433/pdfgeneration treefixed pointspermutationsrandom generationderangements[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Philippe Duchon Romaric Duvignau A new generation tree for permutations, preserving the number of fixed points Discrete Mathematics & Theoretical Computer Science 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] |
| title | A new generation tree for permutations, preserving the number of fixed points |
| title_full | A new generation tree for permutations, preserving the number of fixed points |
| title_fullStr | A new generation tree for permutations, preserving the number of fixed points |
| title_full_unstemmed | A new generation tree for permutations, preserving the number of fixed points |
| title_short | A new generation tree for permutations, preserving the number of fixed points |
| title_sort | new generation tree for permutations preserving the number of fixed points |
| topic | 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] |
| url | https://dmtcs.episciences.org/2433/pdf |
| work_keys_str_mv | AT philippeduchon anewgenerationtreeforpermutationspreservingthenumberoffixedpoints AT romaricduvignau anewgenerationtreeforpermutationspreservingthenumberoffixedpoints AT philippeduchon newgenerationtreeforpermutationspreservingthenumberoffixedpoints AT romaricduvignau newgenerationtreeforpermutationspreservingthenumberoffixedpoints |