Counting and generating permutations in regular classes of permutationsReport as inadecuate

Counting and generating permutations in regular classes of permutations - Download this document for free, or read online. Document in PDF available to download.

1 Department of Computer Science Oxford

Abstract : The signature of a permutation σ is a word sgσ ⊆ {a, d} * whose ith letter is d when σ has a descent i.e. σi > σi + 1 and is a when σ has an ascent i.e. σi < σi + 1. Combinatorics of permutations with a prescribed signature is quite well explored. Here we introduce regular classes of permutations, the sets ΛL of permutations with signature in regular languages L ⊆ {a, d} * . Given a regular class of permutation we i count the permutations of a given length within the class; ii compute a closed form formula for the exponential generating function; and iii sample uniformly at random the permutation of a given length. We first recall how i is solved in the literature for the case of a single signature. We then explain how to extend these methods to regular classes of permutations using language equations from automata theory. We give two methods to solve ii in terms of exponential of matrices. For the third problem we provide both discrete and continuous recursive methods as well as an extension of Boltzmann sampling to uncountable union of sets parametrised by a variable ranging over an interval. Last but not least, a part of our contributions are based on a geometric interpretation of a subclass of regular timed languages that is, recognised by timed automata specific to our problem.

Author: Nicolas Basset -



Related documents