Preserving the number of cycles of length \(k\) in a growing uniform permutation (Q727199)

Summary: 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\).