Restricted permutations refined by number of crossings and nestings. (English) Zbl 1443.05007
Summary: Let \(\mathrm{st} = \{\mathrm{st}_1, \dots, \mathrm{st}_k\}\) be a set of \(k\) statistics on permutations with \(k \geq 1\). We say that two given subsets of permutations \(T\) and \(T^\prime\) are \(\mathrm{st}\)-Wilf-equivalent if the joint distributions of all statistics in st over the sets of \(T\)-avoiding permutations \(S_n (T)\) and \(T^\prime\)-avoiding permutations \(S_n (T^\prime)\) are the same. The main purpose of this paper is the \((\mathrm{cr}, \mathrm{nes})\)-Wilf-equivalence classes for all single patterns in \(S_3\), where \(\mathrm{cr}\) and \(\mathrm{nes}\) denote respectively the statistics number of crossings and nestings. One of the main tools that we use is the bijection \(\Theta : S_n (321) \to S_n (132)\) which was originally exhibited by S. Elizalde and I. Pak [J. Comb. Theory, Ser. A 105, No. 2, 207–219 (2004; Zbl 1048.05003)]. They proved that the bijection \(\Theta\) preserves the number of fixed points and exceedances. Since the given formulation of \(\Theta\) is not direct, we show that it can be defined directly by a recursive formula. Then, we prove that it also preserves the number of crossings. Due to the fact that the sets of non-nesting permutations and 321-avoiding permutations are the same, these properties of the bijection \(\Theta\) lead to an unexpected result related to the \(q,p\)-Catalan numbers of A. Randrianarivony [Discrete Math. 178, No. 1–3, 199–211 (1998; Zbl 0892.05002)].
Keywords:
bijections; crossings; nestings; restricted permutations; Wilf-equivalence; \(q\)-Catalan numbersSoftware:
AARONReferences:
| [1] | Bloom, J.; Saracino, D., On bijections for pattern-avoiding permutations, J. Combin. Theory Ser. A, 116, 1271-1284 (2009) · Zbl 1181.05002 |
| [2] | Bloom, J.; Saracino, D., Another look at bijections for pattern-avoiding permutations, Adv. Appl. Math., 45, 395-409 (2010) · Zbl 1194.05001 |
| [3] | Burrill, S.; Mishna, M.; Post, J., On k-crossing and k-nesting of permutation, (DMTCS Proc.An (2010)), 593-600 · Zbl 1374.05003 |
| [4] | Cheng, S.; Elizalde, S.; Kasraoui, A.; Sagan, E., Inversion polynomials for 321-avoiding permutations, Adv. Appl. Math., 38, 149-163 (2007) |
| [5] | Claesson, A.; Kitaev, S., Classification of bijections between 321- and 132-avoiding permutations, (DMTCS Proc. AJ (2008)), 495-506 · Zbl 1393.05010 |
| [6] | Corteel, S., Crossing and alignments of permutations, Adv. Appl. Math., 38, 2, 149-163 (2007) · Zbl 1121.05003 |
| [7] | Dokos, T.; Dwyer, T.; Johnson, Bryan P.; Sagan, Bruce E.; Selsor, K., Permutation patterns and statistics, Discrete Math., 312, 18, 2760-2775 (2012) · Zbl 1248.05004 |
| [8] | Elizalde, S., Multiple pattern-avoidance with respect to fixed points and excedances, Electron. J. Combin., 11, #R51 (2004) · Zbl 1055.05003 |
| [9] | Elizalde, S., Fixed points and excedances in restricted permutations, Electron. J. Combin., 18, 2, #P29 (2012) · Zbl 1243.05018 |
| [10] | Elizalde, S.; Deutsch, E., A simple and unusual Bijection for Dyck Paths and its consequences, Ann. Comb., 7, 281-297 (2003) · Zbl 1047.05001 |
| [11] | Elizalde, S.; Pak, I., Bijections for refined restricted permutations, J. Combin. Theory Ser. A, 105, 207-219 (2004) · Zbl 1048.05003 |
| [12] | Knuth, D., The Art of Computer Programming, Vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0302.68010 |
| [13] | Krattenthaler, C., Permutations with restricted patterns and Dyck Paths, Adv. Appl. Math., 27, 510-530 (2001) · Zbl 0994.05001 |
| [14] | Mansour, T.; Shattuck, M., On a recurrence related to 321 avoiding permutations, Notes Number Theory Discrete Math., 20, 2, 74-78 (2014) · Zbl 1344.11017 |
| [15] | de Médicis, A.; Viennot, X. G., Moments des q-polynômes de Laguerre et la bijection de Foata-Zeilberger, Adv. Appl. Math., 15, 262-304 (1994) · Zbl 0812.05074 |
| [16] | Randrianarivony, A., Fractions continues, q-Nombres de Catalan et q-Polynômes de Genocchi, European J. Combin., 18, 75-92 (1997) · Zbl 0872.05001 |
| [17] | Randrianarivony, A., Q, p-analogues des nombres de Catalan, Discrete Math., 178, 199-211 (1998) · Zbl 0892.05002 |
| [18] | Reifegerste, A., Excedances and descents of bi-increasing permutations (2002), arXiv:math/0212247v1 [math.CO] |
| [19] | Robertson, A., Restricted permutations from Catalan to Fine and back, Sémin. Lothar. Combin., 50, B50g (2004) · Zbl 1064.05003 |
| [20] | Robertson, A.; Saracino, D.; Zeilberger, D., Refined restricted permutations, Ann. Comb., 6, 427-444 (2003) · Zbl 1017.05014 |
| [21] | Saracino, D., On two Bijections from \(S_n ( 321 )\) to \(S_n ( 132 )\), Ars Combin., 101, 65-74 (2011) · Zbl 1265.05021 |
| [22] | Simion, R.; Schmidt, F., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.05002 |
| [23] | Stanley, Richard P., (Enumerative Combinatorics. Vol. 2. Enumerative Combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62 (1999)), The Catalan addendum is available at http://www-math.ucdenver.edu/wcherowi/courses/m5793/catadd.pdf · Zbl 0928.05001 |
| [24] | West, J., Permutations with Forbidden Subsequences and Stack-Sortable Permutations (1990), Massachusetts Institute of Technology: Massachusetts Institute of Technology Cambridge, (PHD-thesis) |
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.
