Séminaire Lotharingien de Combinatoire, 78B.19 (2017), 12 pp.
Mathilde Bouvel,
Veronica Guerrini, Andrew Rechnitzer and Simone Rinaldi
Semi-Baxter and Strong-Baxter Permutations
Abstract.
In this paper, we enumerate two families of pattern-avoiding
permutations: those avoiding the vincular pattern
2\underbracket{41}3, which we call semi-Baxter
permutations, and those avoiding the vincular patterns
2\underbracket{41}3,
3\underbracket{14}2 and
3\underbracket{41}2, which we call strong-Baxter
permutations. For each of these families, we describe a generating
tree, which translates into a functional equation for the generating
function. For semi-Baxter permutations, it is solved using (a variant
of) the kernel method, giving an expression for the generating
function and both a closed and a recursive formula for its
coefficients. For strong-Baxter permutations, we show that their
generating function is (a slight modification of) that of a family of
walks in the quarter plane, which is known to be non D-finite.
Received: November 14, 2016.
Accepted: February 17, 2017.
Final version: April 1, 2017.
The following versions are available: