SEMI-BAXTER AND STRONG-BAXTER: TWO RELATIVES OF THE BAXTER SEQUENCE

作     者：Bouvel, Mathilde Guerrini, Veronica Rechnitzer, Andrew Rinaldi, Simone 

作者机构：Univ Zurich Inst Math CH-8057 Zurich Switzerland Univ Siena Dept Informat Engn & Math I-53100 Siena Italy Univ British Columbia Dept Math Vancouver BC V6T 1Z2 Canada 

出 版 物：《SIAM JOURNAL ON DISCRETE MATHEMATICS》 (工业与应用数学会离散数学杂志)

年 卷 期：2018年第32卷第4期

页      面：2795-2819页

核心收录：

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主　　题：enumerative combinatorics permutations generating functions 

摘      要：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.