The goal of this work is to describe a uniform generation tree for permutations which preserves the number of $k$-cycles between any permutation (except for a small unavoidable subset of optimal size) of the tree and its direct children. Moreover, the tree we describe has the property that if the number of $k$-cycles does not change during any $k$ consecutive levels, then any further random descent will always yield permutations with that same number of $k$-cycles. This specific additional property yields interesting applications for exact sampling. We describe a new random generation algorithm for permutations with a fixed number of $k$-cycles in $n+\mathcal{O}(1)$ expected calls to a random integer sampler. Another application is a combinatorial algorithm for exact sampling from the Poisson distribution with parameter $1/k$.
@article{10_37236_6014,
author = {Philippe Duchon and Romaric Duvignau},
title = {Preserving the number of cycles of length \(k\) in a growing uniform permutation},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {4},
doi = {10.37236/6014},
zbl = {1351.05126},
url = {http://geodesic.mathdoc.fr/articles/10.37236/6014/}
}
TY - JOUR
AU - Philippe Duchon
AU - Romaric Duvignau
TI - Preserving the number of cycles of length \(k\) in a growing uniform permutation
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/6014/
DO - 10.37236/6014
ID - 10_37236_6014
ER -
%0 Journal Article
%A Philippe Duchon
%A Romaric Duvignau
%T Preserving the number of cycles of length \(k\) in a growing uniform permutation
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/6014/
%R 10.37236/6014
%F 10_37236_6014
Philippe Duchon; Romaric Duvignau. Preserving the number of cycles of length \(k\) in a growing uniform permutation. The electronic journal of combinatorics, Tome 23 (2016) no. 4. doi: 10.37236/6014
