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.

Bouvel, M., Guerrini, V., Rechnitzer, A., Rinaldi, S. (2018). Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence. SIAM JOURNAL ON DISCRETE MATHEMATICS, 32(4), 2795-2819 [10.1137/17M1126734].

### Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence

#### 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. 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.
##### Scheda breve Scheda completa Scheda completa (DC)
2018
Bouvel, M., Guerrini, V., Rechnitzer, A., Rinaldi, S. (2018). Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence. SIAM JOURNAL ON DISCRETE MATHEMATICS, 32(4), 2795-2819 [10.1137/17M1126734].
File in questo prodotto:
File
Bouvel-2018-Semi-baxter-and-strong-baxter-two-r.pdf

non disponibili

Tipologia: PDF editoriale
Licenza: NON PUBBLICO - Accesso privato/ristretto
Dimensione 489.24 kB
Utilizza questo identificativo per citare o creare un link a questo documento: `https://hdl.handle.net/11365/1066607`