On a refinement of Wilf-equivalence for permutations. (English) Zbl 1307.05004
Summary: Recently, T. Dokos et al. [Discrete Math. 312, No. 18, 2760–2775 (2012; Zbl 1248.05004)] conjectured that for all \(k, m\geqslant 1\), the patterns \( 12 \ldots k(k+m+1)\ldots (k+2)(k+1) \) and \((m+1)(m+2)\ldots(k+m+1)m\ldots 21\) are \(maj\)-Wilf-equivalent. In this paper, we confirm this conjecture for all \(k\geqslant 1\) and \(m=1\). In fact, we construct a descent set preserving bijection between \( 12\ldots k (k-1) \)-avoiding permutations and \(23\ldots k1\)-avoiding permutations for all \(k\geqslant 3\). As a corollary, our bijection enables us to settle a conjecture of N. Gowravaram and R. Jagadeesan [ibid. 20, No. 4, Research Paper P17, 28 p. (2013; Zbl 1300.05319)] concerning the Wilf-equivalence for permutations with given descent sets.
References:
| [1] | E. Babson, J. West, and G. Xin. Wilf-equivalence for singleton classes. {\it Adv. Appl.} {\it Math.}, 38:133-148, 2007. · Zbl 1127.05002 |
| [2] | J. Bloom, D. Saracino. On bijections for pattern-avoiding permutations. {\it J. Combin.} {\it Theory Ser. A}, 116:1271-1284, 2009. · Zbl 1181.05002 |
| [3] | J. Bloom, D. Saracino. Another look at bijections for pattern-avoiding permutations. {\it Adv. Appl. Math.}, 45:395-409, 2010. · Zbl 1194.05001 |
| [4] | J. Bloom. A refinement of Wilf-equivalence for patterns of length 4. {\it J. Combin.} {\it Theory Ser. A}, 124:166-177, 2014. · Zbl 1283.05012 |
| [5] | M. B´ona. Combinatorics of Permutations. {\it CRC Press}, 2004. · Zbl 1052.05001 |
| [6] | M. B´ona. On a family of conjectures of Joel Lewis on alternating Permutations. {\it Graphs Combin.}, 30:521-526, 2014. · Zbl 1296.05002 |
| [7] | A. Claesson, S. Kitaev. Classification of bijections between 321-and 132-avoiding permutations. {\it S´em. Lothar. Combin.}, 60: Art. B60d, 2008/09. · Zbl 1179.05006 |
| [8] | E. Deutsch, A. Robertson, D. Saracino. Refined restricted involutions. {\it European J.} {\it Combin.}, 28:481-498, 2007. · Zbl 1110.05003 |
| [9] | T. Dokos, T. Dwyer, B. P. Johnson, B.E. Sagan, K. Selsor. Permutation patterns and statistics. {\it Discrete Math.}, 312: 2760-2775, 2012. · Zbl 1248.05004 |
| [10] | S. Elizalde. Fixed points and exceedances in restricted permutations. {\it Electron. J.} {\it Combin.}, 18: P29, 2011. · Zbl 1243.05018 |
| [11] | N. Gowravaram and R. Jagadeesan. Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux. {\it Electron. J. Combin.}, 20(4): #P17, 2013. · Zbl 1300.05319 |
| [12] | S. Kitaev. Patterns in permutations and words. {\it Springer Verlag (EATCS mono-} {\it graphs in Theoretical Computer Science book series)}, 2011. · Zbl 1257.68007 |
| [13] | J. B. Lewis. Generating trees and pattern avoidance in alternating permutations. {\it Electronic J. Combin.}, 19(1):P21, 2012. · Zbl 1243.05011 |
| [14] | A. Robertson, D. Saracino, D. Zeilberger.Refined restricted permutations. {\it Ann.Comb.}, 6:427-444, 2002. · Zbl 1017.05014 |
| [15] | J. West. Permutations with forbidden subsequences and stack-sortable permutations. {\it Ph.D. thesis, Massachuetts Institute of Technology}, 1990. |
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.
