DOAJ Open Access 2014

A new generation tree for permutations, preserving the number of fixed points

Philippe Duchon Romaric Duvignau

Lihat Sumber DOI

Abstrak

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.

Topik & Kata Kunci

Mathematics

Penulis (2)

Philippe Duchon

Romaric Duvignau

Format Sitasi

APA MLA BibTeX

Duchon, P., Duvignau, R. (2014). A new generation tree for permutations, preserving the number of fixed points. https://doi.org/10.46298/dmtcs.2433

Akses Cepat

Lihat di Sumber doi.org/10.46298/dmtcs.2433

Informasi Jurnal

Tahun Terbit: 2014
Sumber Database: DOAJ
DOI: 10.46298/dmtcs.2433
Akses: Open Access ✓