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: