Refined restricted involutions. (English) Zbl 1110.05003
Let \(I_n^k(\alpha)\) denote the set of involutions on \(\{1,\dots,n\}\) with \(k\) fixed points which avoid the pattern \(\alpha\), and \(I_n^k(\emptyset;\alpha)\) the set of such involutions in which \(\alpha\) occurs exactly once. The authors deal with the enumeration of these sets for all patterns of length 3.
By a result of R. Simion and F. Schmidt [Eur. J. Comb. 6, 383-406 (1985; Zbl 0615.05002)], all the patterns \(123\), \(132\), \(213\), and \(321\) are avoided by \({n\choose\lfloor n/2\rfloor}\) involutions in \(S_n\), whereas \(231\) and \(312\) are avoided by \(2^{n-1}\) \(n\)-involutions. Using the tool of standard Young tableaux, the authors refine the enumeration according to the number of fixed points. In particular, it is shown that \[ | I_n^k(132)| =| I_n^k(213)| =| I_n^k(321)| ,\;| I_n^k(231)| =| I_n^k(312)| \text{ for all }0\leq k\leq n. \] This also refines the analogous result for \(n\)-permutations given by the last two authors and D. Zeilberger [Ann. Comb. 6, No. 3-4, 427-444 (2002; Zbl 1017.05014)].
In the second part of the paper, the numbers \(| I_n^k(\emptyset;\alpha)| \) are determined explicitly for any \(\alpha\in S_3\).
By a result of R. Simion and F. Schmidt [Eur. J. Comb. 6, 383-406 (1985; Zbl 0615.05002)], all the patterns \(123\), \(132\), \(213\), and \(321\) are avoided by \({n\choose\lfloor n/2\rfloor}\) involutions in \(S_n\), whereas \(231\) and \(312\) are avoided by \(2^{n-1}\) \(n\)-involutions. Using the tool of standard Young tableaux, the authors refine the enumeration according to the number of fixed points. In particular, it is shown that \[ | I_n^k(132)| =| I_n^k(213)| =| I_n^k(321)| ,\;| I_n^k(231)| =| I_n^k(312)| \text{ for all }0\leq k\leq n. \] This also refines the analogous result for \(n\)-permutations given by the last two authors and D. Zeilberger [Ann. Comb. 6, No. 3-4, 427-444 (2002; Zbl 1017.05014)].
In the second part of the paper, the numbers \(| I_n^k(\emptyset;\alpha)| \) are determined explicitly for any \(\alpha\in S_3\).
Reviewer: Astrid Reifegerste (Hannover)
MSC:
| 05A05 | Permutations, words, matrices |
| 05A15 | Exact enumeration problems, generating functions |
| 05E10 | Combinatorial aspects of representation theory |
Keywords:
permutation patterns; pattern-avoiding permutations; occurrence of patterns; Dyck paths; Young tableauxSoftware:
AARONReferences:
| [1] | Guibert, O.; Mansour, T., Restricted 132-involutions and Chebyshev polynomials (2002) |
| [2] | Guibert, O.; Mansour, T., Some statistics on restricted 132 involutions (2002) · Zbl 1017.05009 |
| [3] | Knuth, D. E., The Art of Computer Programming, vol. 3 (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903 |
| [4] | Knuth, D. E., Permutations, matrices, and generalized Young tableaux, Pacific J. Math., 34, 709-727 (1970) · Zbl 0199.31901 |
| [5] | Krattenthaler, C., Permutations with restricted patterns and Dyck paths, Adv. Appl. Math., 27, 510-530 (2001) · Zbl 0994.05001 |
| [6] | Mansour, T.; Robertson, A., Refined restricted permutations avoiding subsets of patterns of length three (2002) · Zbl 1017.05011 |
| [7] | Robertson, A.; Saracino, D.; Zeilberger, D., Refined restricted permutations (2002) · Zbl 1017.05014 |
| [8] | Schensted, C., Longest increasing and decreasing subsequences, Canad. J. Math., 13, 179-191 (1961) · Zbl 0097.25202 |
| [9] | Simion, R.; Schmidt, F., Restricted permutations, European J. Combin., 6, 383-406 (1985) · Zbl 0615.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.
