Dyck paths and restricted permutations. (English) Zbl 1094.05001
Summary: This paper is devoted to characterize permutations with forbidden patterns by using canonical reduced decompositions, which leads to bijections between Dyck paths and \(S_{n}\)(321) and \(S_{n}\)(231), respectively. We also discuss permutations in \(S_{n}\) avoiding two patterns, one of length 3 and the other of length \(k\). These permutations produce a kind of discrete continuity between the Motzkin and the Catalan numbers.
MSC:
| 05A05 | Permutations, words, matrices |
| 05A15 | Exact enumeration problems, generating functions |
| 30B70 | Continued fractions; complex-analytic aspects |
| 42C05 | Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis |
Software:
AARONReferences:
| [1] | Bandlow, J.; Killpatrick, K., An area-to-inv bijection Dyck paths and 312-avoiding permutations, Electron. J. Combin., 8, #R40 (2001) · Zbl 0981.05006 |
| [2] | Barcucci, E.; Del Lungo, A.; Pergola, E.; Pinzani, R., ECO: a methodology for enumeration of combinatorial objects, J. Differential Equation Appl., 5, 435-490 (1999) · Zbl 0944.05005 |
| [3] | Barcucci, E.; Del Lungo, A.; Pergola, E.; Pinzani, R., From Motzkin to Catalan permutations, Discrete Math., 217, 33-49 (2000) · Zbl 0965.05004 |
| [4] | Chen, W. Y.C.; Deng, Y. P.; Yang, L. L.M., Motzkin paths and reduced decompositions for permutations with forbidden patterns, Electron. J. Combin., 9, 2, #R15 (2003) · Zbl 1023.05002 |
| [5] | Chow, T.; West, J., Forbidden subsequences and Chebyshev polynomials, Discrete Math., 204, 119-128 (1999) · Zbl 0932.05007 |
| [6] | Krattenthaler, C., Permutations with restricted patterns and Dyck paths, Adv. Appl. Math., 27, 510-530 (2001) · Zbl 0994.05001 |
| [7] | A. Lascoux, Lecture Notes on the Symmetric Group, Nankai University, 2002.; A. Lascoux, Lecture Notes on the Symmetric Group, Nankai University, 2002. |
| [8] | T. Mansour, Restricted even permutations and Chebyshev polynomials, preprint math.CO/0302014.; T. Mansour, Restricted even permutations and Chebyshev polynomials, preprint math.CO/0302014. · Zbl 1093.05002 |
| [9] | Mansour, T.; Vainshtein, A., Restricted permutations, continued fractions, and Chebyshev polynomials, Electron. J. Combin., 7, #R17 (2000) · Zbl 0940.05001 |
| [10] | Mansour, T.; Vainshtein, A., Restricted 132-avoiding permutations, Adv. Appl. Math., 126, 258-269 (2001) · Zbl 0982.05002 |
| [11] | Mansour, T.; Vainshtein, A., Layered restrictions and Chebychev polynomials, Ann. Combin., 5, 451-458 (2001) · Zbl 0988.05003 |
| [12] | Mansour, T.; Vainshtein, A., Restricted permutations and Chebyshev polynomials, Séminaire Lotharingien de Combinatoire, 47 (2002), Article B47c · Zbl 1022.05005 |
| [13] | Rivlin, Th., Chebyshev polynomials. From Approximation Theory to Algebra and Number Theory (1990), Wiley: Wiley New York · Zbl 0734.41029 |
| [14] | Robertson, A.; Saracino, D.; Zeilberger, D., Refined restricted permutations, Ann. Combin., 6, 427-444 (2002) · Zbl 1017.05014 |
| [15] | Simion, R.; Schmodt, F. W., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.05002 |
| [16] | West, J., Generating trees and forbidden subsequences, Discrete Math., 157, 363-372 (1996) · Zbl 0877.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.
