Semi-Baxter and Strong-Baxter: Two Relatives of the Baxter Sequence

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. We call semi-Baxter numbers and strong-Baxter numbers the associated enumeration sequences. We prove that the semi-Baxter numbers enumerate in addition plane permutations (avoiding $2\underbracket{14}3$). The problem of counting these permutations was open and has given rise to several conjectures, which we also prove in this paper. For each family (that of semi-Baxter---or, equivalently, plane---and that of strong-Baxter permutations), 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: this gives an expression for the generating function while also proving its D-finiteness. From the obtained generating function, we derive closed formulas for the semi-Baxter numbers, a recurrence that they satisfy, as well as their asymptotic behavior. 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.