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 (41) under bar 3, which we call semi-Baxter permutations, and those avoiding the vincular patterns 2 (41) under bar 3, 3 (14) under bar 2, and 3 (41) under bar 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 (14) under bar 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.