Counting pattern avoiding permutations by number of movable letters. (English) Zbl 1499.05046
Summary: By a movable letter within a pattern avoiding permutation, we mean one that may be transposed with its predecessor while still avoiding the pattern. In this paper, we enumerate permutations avoiding a single pattern of length three according to the number of movable letters, thereby obtaining new \(q\)-analogues of the Catalan number sequence. Indeed, we consider the joint distribution with the statistics recording the number of descents and occurrences of certain vincular patterns. To establish several of our results, we make use of the kernel method to solve the functional equations that arise.
References:
| [1] | E. Babson, E. Steingrìmsson: Generalized permutation patterns and a classification of Mahonian statistics. Sém. Lothar. Combin. 44 (2000), Art. B44b. · Zbl 0957.05010 |
| [2] | M. Barnabei, F. Bonetti, M. Silimbani: The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2. European J. Combin. 31(5) (2010), 1360-1371. · Zbl 1230.05016 |
| [3] | A. Baxter: Refining enumeration schemes to count according to permutation statis-tics. Electron. J. Combin. 21(2) (2014), #P2.50. · Zbl 1300.05026 |
| [4] | M. Bóna: The absence of a pattern and the occurrences of another. Discrete Math. Theor. Comput. Sci. 12(2) (2010), 89-102. · Zbl 1278.05007 |
| [5] | M. Bóna: Surprising symmetries in objects counted by Catalan numbers. Electron. J. Combin. 19(1) (2012), #P62. · Zbl 1243.05006 |
| [6] | A. Burstein, S. Elizalde: Total occurrence statistics on restricted permutations. Pure Math. Appl. (PU.M.A.) 24 (2013), 103-123. · Zbl 1313.05017 |
| [7] | A. Claesson, S. Kitaev: Classification of bijections between 321-and 132-avoiding pemutations. Sém. Lothar. Combin. 60 (2008), Art. B60d. · Zbl 1393.05010 |
| [8] | A. M. Goyt, D. Mathisen: Permutation statistics and q-Fibonacci numbers. Elec-tron. J. Combin. 16 (2009), #R101. · Zbl 1188.05023 |
| [9] | C. Homberger: Expected patterns in permutation classes. Electron. J. Combin. 19(3) (2012), #P43. · Zbl 1253.05009 |
| [10] | Q. Hou, T. Mansour: Kernel method and linear recurrence system. J. Comput. Appl. Math. 261(1) (2008), 227-242. · Zbl 1138.65108 |
| [11] | M. Hyatt, J. Remmel: The classification of 231-avoiding permutations by descents and maximum drop. J. Comb. 6(4) (2015), 509-534. · Zbl 1325.05020 |
| [12] | S. Kitaev: Patterns in Permutations and Words. Springer-Verlag, Berlin, 2011. · Zbl 1257.68007 |
| [13] | T. Mansour: Restricted 1-3-2 permutations and generalized patterns. Ann. Comb. 6 (2002), 65-76. · Zbl 1009.05002 |
| [14] | A. Mendes, J. Remmel: Permutations and words counted by consecutive patterns. Adv. in Appl. Math. 37(4) (2006), 443-480. · Zbl 1110.05005 |
| [15] | A. Robertson, D. Saracino, D. Zeilberger: Refined restricted permutations. Ann. Comb. 6 (2002), 427-444. · Zbl 1017.05014 |
| [16] | R. Simion, F. W. Schmidt: Restricted permutations. European J. Combin. 6 (1985), 383-406. · Zbl 0615.05002 |
| [17] | N. J. A. Sloane: On-line Encyclopedia of Integer Sequences. http://oeis.org, 2010. · Zbl 1044.11108 |
| [18] | V. Vajnovszki: The equidistribution of some length three vincular patterns on Sn(132). Inform. Process. Lett. 130 (2018), 40-45 · Zbl 1421.05009 |
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.
