Counting and Generating Permutations in Regular Classes

Abstract

The signature of a permutation $\sigma$ is a word $\mathtt {sg}(\sigma )\subseteq \{\mathfrak {a},\mathfrak {d}\}^*$ with ith letter $\mathfrak {d}$ when $\sigma$ has a descent [i.e. $\sigma (i)>\sigma (i+1)$] and $\mathfrak {a}$ when $\sigma$ has an ascent [i.e. $\sigma (i)<\sigma (i+1)$]. The combinatorics of permutations with a prescribed signature is quite well explored. Here we introduce regular classes of permutations, the sets $\varLambda (L)$ of permutations with signature in regular languages $L\subseteq \{\mathfrak {a},\mathfrak {d}\}^*$. Given a regular class of permutations 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 exponentials 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).