An infinite family of inv-Wilf-equivalent permutation pairs. (English) Zbl 1302.05001
Summary: Wilf-equivalence is one of the central concepts of pattern-avoiding permutations, and has been studied for more than thirty years. The two known infinite families of Wilf-equivalent permutation pairs, due to Stankova-West and Backelin-West-Xin, both satisfy the stronger condition of shape-Wilf-equivalence. T. Dokos et al. [Discrete Math. 312, No. 18, 2760–2775 (2012; Zbl 1248.05004)] recently studied a different strengthening of Wilf-equivalence called inv-Wilf-equivalence, which takes account of the inversion number of a permutation. They conjectured that all inv-Wilf-equivalent permutation pairs arise from trivial symmetries. We disprove this conjecture by constructing an infinite family of counterexamples derived from the permutation pair 231 and 312. The key to this construction is to generalize simultaneously the concepts of shape-Wilf-equivalence and inv-Wilf-equivalence. A further consequence is a proof of the recent Baxter-Jaggard conjecture on even-shape-Wilf-equivalent permutation pairs.
Citations:
Zbl 1248.05004References:
| [2] | Backelin, J.; West, J.; Xin, G., Wilf-equivalence for singleton classes, Adv. Appl. Math., 38, 133-148 (2007) · Zbl 1127.05002 |
| [3] | Baxter, A.; Jaggard, A. D., Pattern avoidance by even permutations, Electron. J. Combin., 18, 15 (2011), Paper 28 · Zbl 1243.05005 |
| [4] | Bloom, J.; Elizalde, S., Pattern avoidance in matchings and partitions, Electron. J. Combin., 20, 38 (2013), Paper 5 · Zbl 1267.05021 |
| [6] | Bóna, M., Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps, J. Combin. Theory Ser. A, 80, 257-272 (1997) · Zbl 0887.05004 |
| [7] | Bousquet-Mélou, M., Counting permutations with no long monotone subsequence via generating trees and the kernel method, J. Algebraic Combin., 33, 571-608 (2011) · Zbl 1226.05003 |
| [8] | 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. Amer. Math. Soc., 359, 1555-1575 (2007) · Zbl 1108.05012 |
| [9] | Claesson, A.; Kitaev, S., Classification of bijections between 321- and 132-avoiding permutations, (20th Annual International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2008. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics, FPSAC 2008, Discrete Math. Theor. Comput. Sci. Proc., AJ (2008), Assoc. Discrete Math. Theor. Comput. Sci.: Assoc. Discrete Math. Theor. Comput. Sci. Nancy), 495-506 · Zbl 1393.05010 |
| [10] | Dokos, T.; Dwyer, T.; Johnson, B. P.; Sagan, B. E.; Selsor, K., Permutation patterns and statistics, Discrete Math., 312, 2760-2775 (2012) · Zbl 1248.05004 |
| [11] | Gessel, I. M., Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A, 53, 257-285 (1990) · Zbl 0704.05001 |
| [12] | Jelínek, V., Dyck paths and pattern-avoiding matchings, European J. Combin., 28, 202-213 (2007) · Zbl 1106.05004 |
| [13] | Knuth, D. E., The Art of Computer Programming, Vol. 1 (1969), Addison-Wesley: Addison-Wesley Reading, MA, London, Don Mills, Ont. · Zbl 0191.18001 |
| [14] | Knuth, D. E., The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA, London, Don Mills, Ont · Zbl 0302.68010 |
| [15] | Krattenthaler, C., Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. Appl. Math., 37, 404-431 (2006) · Zbl 1108.05095 |
| [16] | Rotem, D., On correspondence between binary trees and a certain type of permutation, Inform. Process. Lett., 4, 58-61 (1975) · Zbl 0323.05006 |
| [17] | Simion, R.; Schmidt, F., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.05002 |
| [18] | Stankova, Z., Forbidden subsequences, Discrete Math., 132, 291-316 (1994) · Zbl 0810.05011 |
| [19] | Stankova, Z.; West, J., A new class of Wilf-equivalent permutations, J. Algebraic Combin., 15, 271-290 (2002) · Zbl 1005.05002 |
| [21] | West, J., Generating trees and the Catalan and Schröder numbers, Discrete Math., 146, 247-262 (1995) · Zbl 0841.05002 |
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.
