Semi-Baxter and Strong-Baxter Permutations

Mathilde Bouvel   ; Veronica Guerrini   ; Andrew Rechnitzer   ; Simone Rinaldi

Séminaire lotharingien de combinatoire, 78B (2017)

Résumé

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.