Restricted involutions and Motzkin paths. (English) Zbl 1225.05242
Summary: We show how a bijection due to Biane between involutions and labelled Motzkin paths yields bijections between Motzkin paths and two families of restricted involutions that are counted by Motzkin numbers, namely, involutions avoiding 4321 and 3412. As a consequence, we derive characterizations of Motzkin paths corresponding to involutions avoiding either 4321 or 3412 together with any pattern of length 3. Furthermore, we exploit the described bijection to study some notable subsets of the set of restricted involutions, namely, fixed point free and centrosymmetric restricted involutions.
MSC:
| 05E15 | Combinatorial aspects of groups and algebras (MSC2010) |
| 05A15 | Exact enumeration problems, generating functions |
| 20B35 | Subgroups of symmetric groups |
Software:
OEISOnline Encyclopedia of Integer Sequences:
Motzkin numbers: number of ways of drawing any number of nonintersecting chords joining n (labeled) points on a circle.References:
| [1] | Biane, P., Permutations suivant le type dʼexcédance et le nombre dʼinversions et interprétation combinatoire dʼune fraction continue de Heine, European J. Combin., 14, 277-284 (1993) · Zbl 0784.05005 |
| [2] | Chen, W. Y.C. |
| [3] | Deutsch, E.; Robertson, A.; Saracino, D., Refined restricted involutions, European J. Combin., 28, 481-498 (2007) · Zbl 1110.05003 |
| [4] | de Médicis, A.; Viennot, X. G., Moments des \(q\)-polynômes de Laguerre et la bijection de Foata-Zeilberger, Adv. in Appl. Math., 15, 262-304 (1994) · Zbl 0812.05074 |
| [5] | Egge, E. S., Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials, Adv. in Appl. Math., 33, 451-475 (2004) · Zbl 1059.05004 |
| [6] | Egge, E. S., Restricted symmetric permutations, Ann. Comb., 11, 405-434 (2007) · Zbl 1141.05003 |
| [7] | Foata, D.; Zeilberger, D., Denertʼs permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math., 83, 31-59 (1990) · Zbl 0738.05001 |
| [8] | Françon, J.; Viennot, X. G., Permutations selon leurs pics, creux, doubles montées et double descentes, nombres dʼEuler et nombres de Genocchi, Discrete Math., 28, 21-35 (1979) · Zbl 0409.05003 |
| [9] | O. Guibert, Combinatoire de les permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, PhD thesis, Univ. Bordeaux 1, 1995.; O. Guibert, Combinatoire de les permutations à motifs exclus en liaison avec mots, cartes planaires et tableaux de Young, PhD thesis, Univ. Bordeaux 1, 1995. |
| [10] | Guibert, O.; Mansour, T., Restricted 132-involutions, Sem. Lothar. Combin., 48 (2002), Art. B48a, 23 pp. (electronic) · Zbl 1017.05009 |
| [11] | Guibert, O.; Pergola, E., Enumeration of vexillary involutions which are equal to their mirror/complement, Discrete Math., 224, 281-287 (2000) · Zbl 0963.05009 |
| [12] | Guibert, O.; Pergola, E.; Pinzani, R., Vexillary involutions are enumerated by Motzkin numbers, Ann. Comb., 5, 153-174 (2001) · Zbl 0988.05001 |
| [13] | Jaggard, A. D., Prefix exchanging and pattern avoidance by involutions, Electron. J. Combin., 9 (2002/2003), Research paper 16, 24 pp. (electronic) · Zbl 1045.05002 |
| [14] | Krattenthaler, C., Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math., 27, 510-530 (2001) · Zbl 0994.05001 |
| [15] | Mansour, T.; West, J., Avoiding 2-letter signed patterns, Sem. Lothar. Combin., 49 (2002/2004), Art. B49a, 11 pp. (electronic) · Zbl 1031.05003 |
| [16] | Regev, A., Asymptotic values for degrees associated with strips of Young tableau, Adv. Math., 41, 115-136 (1981) · Zbl 0509.20009 |
| [17] | Simion, R., Combinatorial statistics on type-B analogue of noncrossing partitions and restricted permutations, Electron. J. Combin., 7, 383-406 (2000) |
| [18] | Simion, R.; Schmidt, F. W., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.05002 |
| [19] | Sloane, N. J.A., The on-line encyclopedia of integer sequences · Zbl 1274.11001 |
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.
