×

Pattern-avoiding inversion sequences and open partition diagrams. (English) Zbl 1459.05004

Summary: By using the generating tree technique and the obstinate kernel method, D. Kim and Z. Lin [Sémin. Lothar. Comb. 78B, 78B.52, 12 p. (2017; Zbl 1385.05011)] confirmed a conjecture due to M. Martinez and C. Savage [J. Integer Seq. 21, No. 2, Article 18.2.2, 44 p. (2018; Zbl 1384.05008)] which asserts that inversion sequences \(e = (e_1, e_2, \ldots, e_n)\) containing no three indices \(i < j < k\) such that \(e_i \geq e_j, e_j \geq e_k\) and \(e_i > e_k\) are counted by Baxter numbers. In this paper, we provide a bijective proof of this conjecture via an intermediate structure of open partition diagrams, in answer to a problem posed by Beaton-Bouvel-Guerrini-Rinaldi. Moreover, we show that two new classes of pattern-avoiding inversion sequences are also counted by Baxter numbers.

MSC:

05A05 Permutations, words, matrices
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Babson, E.; Steingrímsson, E., Generalized permutation patterns and a classification of the Mahonian statistics, Sémin. Lothar. Comb. B, 44 (2000), 18 pp · Zbl 0957.05010
[2] Beaton, N. R.; Bouvel, M.; Guerrini, V.; Rinaldi, S., Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, Theor. Comput. Sci., 777, 69-92 (2019) · Zbl 1427.05003
[3] Bóna, M., Combinatorics of Permutations (2004), CRC Press · Zbl 1052.05001
[4] Bonichon, N.; Bousquet-Mélou, M.; Fusy, É., Baxter permutations and plane bipolar orientations, Sémin. Lothar. Comb., 61A (2009/2011), Art. B61Ah · Zbl 1205.05004
[5] Bousquet-Mélou, M., Four classes of pattern-avoiding permutations under one roof: generating trees with two labels, Electron. J. Comb., 9 (2003), #R19 · Zbl 1031.05006
[6] Bouvel, M.; Guibert, O., Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry, Ann. Comb., 18, 199-232 (2014) · Zbl 1295.05009
[7] Burrill, S.; Courtiel, J.; Fusy, É.; Melczer, S.; Mishna, M., Tableau sequences, open diagrams, and Baxter families, Eur. J. Comb., 58, 144-165 (2016) · Zbl 1343.05161
[8] Burrill, S.; Elizalde, S.; Mishna, M.; Yen, L., A generating tree approach to k-nonnesting partitions and permutations, Ann. Comb., 20, 453-485 (2016) · Zbl 1347.05006
[9] Cao, W.; Jin, E. Y.; Lin, Z., Enumeration of inversion sequences avoiding triples of relations, Discrete Appl. Math., 260, 86-97 (2019) · Zbl 1409.05028
[10] Chen, W. Y.C.; Deng, E. Y.P.; Du, R. R.X.; Stanley, R. P.; Yan, C. H., Crossings and nestings of matchings and partitions, Trans. Am. Math. Soc., 359, 1555-1575 (2007) · Zbl 1108.05012
[11] Chung, F.; Graham, R.; Hoggatt, V.; Kleiman, M., The number of Baxter permutations, J. Comb. Theory, Ser. A, 24, 382-394 (1978) · Zbl 0398.05003
[12] Corteel, S.; Martinez, M.; Savage, C. D.; Weselcouch, M., Patterns in inversion sequences I, Discrete Math. Theor. Comput. Sci., 18 (2016), #2 · Zbl 1348.05018
[13] Felsner, S.; Fusy, É.; Noy, M.; Orden, D., Bijections for Baxter families and related objects, J. Comb. Theory, Ser. A, 118, 993-1020 (2011) · Zbl 1238.05010
[14] Kitaev, S., Patterns in Permutations and Words (2011), Springer Science & Business Media · Zbl 1257.68007
[15] Kim, D.; Lin, Z., Refined restricted inversion sequences (extended abstract at FPSAC2017), Sémin. Lothar. Comb., 78B, Article 52 pp. (2017) · Zbl 1385.05011
[16] Krattenthaler, C., Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. Appl. Math., 37, 404-431 (2006) · Zbl 1108.05095
[17] Lin, Z., Restricted inversion sequences and enhanced 3-noncrossing partitions, Eur. J. Comb., 70, 202-211 (2018) · Zbl 1384.05045
[18] Mansour, T.; Shattuck, M., Pattern avoidance in inversion sequences, Pure Math. Appl., 25, 157-176 (2015) · Zbl 1374.05019
[19] Martinez, M.; Savage, C. D., Patterns in inversion sequences II: inversion sequences avoiding triples of relations, J. Integer Seq., 21 (2018), Article 18.2.2 · Zbl 1384.05008
[20] Yan, S. H.F., Bijections for inversion sequences, ascent sequences and 3-nonnesting set partitions, Appl. Math. Comput., 325, 24-30 (2018) · Zbl 1428.05031
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.