Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels

Mireille Bousquet-Mélou

The electronic journal of combinatorics, Permutation Patterns, Tome 9 (2002) no. 2

Résumé

Many families of pattern-avoiding permutations can be described by a generating tree in which each node carries one integer label, computed recursively via a rewriting rule. A typical example is that of $123$-avoiding permutations. The rewriting rule automatically gives a functional equation satisfied by the bivariate generating function that counts the permutations by their length and the label of the corresponding node of the tree. These equations are now well understood, and their solutions are always algebraic series. Several other families of permutations can be described by a generating tree in which each node carries two integer labels. To these trees correspond other functional equations, defining 3-variate generating functions. We propose an approach to solving such equations. We thus recover and refine, in a unified way, some results on Baxter permutations, $1234$-avoiding permutations, $2143$-avoiding (or: vexillary) involutions and $54321$-avoiding involutions. All the generating functions we obtain are D-finite, and, more precisely, are diagonals of algebraic series. Vexillary involutions are exceptionally simple: they are counted by Motzkin numbers, and thus have an algebraic generating function. In passing, we exhibit an interesting link between Baxter permutations and the Tutte polynomial of planar maps.

Détail

DOI : 10.37236/1691

Classification : 05A15, 05A10
Mots-clés : generating function, algebraic series, geneating tree, Motzkin numbers, Baxter permutations, Tutte polynomial