Geodesic
A new generation tree for permutations, preserving the number of fixed points
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (2014).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2014_special_265_a58,
     author = {Duchon, Philippe and Duvignau, Romaric},
     title = {A new generation tree for permutations, preserving the number of fixed points},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)},
     year = {2014},
     doi = {10.46298/dmtcs.2433},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2433/}
}
TY  - JOUR
AU  - Duchon, Philippe
AU  - Duvignau, Romaric
TI  - A new generation tree for permutations, preserving the number of fixed points
JO  - Discrete mathematics & theoretical computer science
PY  - 2014
VL  - DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2433/
DO  - 10.46298/dmtcs.2433
LA  - en
ID  - DMTCS_2014_special_265_a58
ER  - 
%0 Journal Article
%A Duchon, Philippe
%A Duvignau, Romaric
%T A new generation tree for permutations, preserving the number of fixed points
%J Discrete mathematics & theoretical computer science
%D 2014
%V DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2433/
%R 10.46298/dmtcs.2433
%G en
%F DMTCS_2014_special_265_a58
Duchon, Philippe; Duvignau, Romaric. A new generation tree for permutations, preserving the number of fixed points. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014), DMTCS Proceedings vol. AT, 26th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2014) (2014). doi : 10.46298/dmtcs.2433. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.2433/

Cité par Sources :