Using functional equations to enumerate 1324-avoiding permutations. (English) Zbl 1295.05015
Summary: We consider the problem of enumerating permutations with exactly \(r\) occurrences of the pattern 1324 and derive functional equations for this general case as well as for the pattern avoidance \((r=0)\) case. The functional equations lead to a new algorithm for enumerating length \(n\) permutations that avoid 1324. This approach is used to enumerate the 1324-avoiders up to \(n=31\). We also extend those functional equations to account for the number of inversions and derive analogous algorithms.
MSC:
| 05A05 | Permutations, words, matrices |
| 05A15 | Exact enumeration problems, generating functions |
| 39B99 | Functional equations and inequalities |
Online Encyclopedia of Integer Sequences:
Number of 1324-avoiding permutations of length n.Number of permutations of length n containing exactly 1 occurrence of the pattern 1324.
References:
| [1] | Albert, M. H.; Elder, M.; Rechnitzer, A.; Westcott, P.; Zabrocki, M., On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia, Adv. in Appl. Math., 36, 2, 96-105 (2006) · Zbl 1089.05002 |
| [2] | Arratia, Richard, On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern, Electron. J. Combin., 6, N1 (1999), Note, 4 pp. (electronic) · Zbl 0922.05002 |
| [3] | Bóna, Miklós, Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps, J. Combin. Theory Ser. A, 80, 2, 257-272 (1997) · Zbl 0887.05004 |
| [4] | Bóna, Miklós, A new upper bound for 1324-avoiding permutations (2012) · Zbl 1298.05019 |
| [5] | Claesson, Anders; Jelínek, Vít; Steingrímsson, Einar, Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns, J. Combin. Theory Ser. A, 119, 8, 1680-1691 (2012) · Zbl 1246.05002 |
| [6] | Elder, Murray; Vatter, Vince, Problems and conjectures presented at the third international conference on permutation patterns (2005) |
| [7] | Gessel, Ira, Symmetric functions and P-recursiveness, J. Combin. Theory Ser. A, 53, 2, 257-285 (1990) · Zbl 0704.05001 |
| [8] | Knuth, Donald E., The Art of Computer Programming. Vol. 1: Fundamental Algorithms (1973), Addison Wesley: Addison Wesley Reading, Massachusetts · Zbl 0302.68010 |
| [9] | Marcus, Adam; Tardos, Gábor, Excluded permutation matrices and the Stanley-Wilf conjecture, J. Combin. Theory Ser. A, 107, 1, 153-160 (2004) · Zbl 1051.05004 |
| [10] | Marinov, Darko; Radoičić, Radoš, Counting 1324-avoiding permutations, Permutation Patterns. Permutation Patterns, Otago, 2003. Permutation Patterns. Permutation Patterns, Otago, 2003, Electron. J. Combin., 9, R13 (2002/03), Research paper, 9 pp. (electronic) · Zbl 1023.05009 |
| [11] | Nakamura, Brian, Approaches for enumerating permutations with a prescribed number of occurrences of patterns, Pure Math. Appl. (PU.M.A.) (2014), in press · Zbl 1313.05007 |
| [12] | Nakamura, Brian; Zeilberger, Doron, Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes, Adv. in Appl. Math., 50, 3, 356-366 (2013) · Zbl 1259.05005 |
| [13] | Regev, Amitai, Asymptotic values for degrees associated with strips of Young diagrams, Adv. Math., 41, 2, 115-136 (1981) · Zbl 0509.20009 |
| [14] | Sloane, Neil, The on-line encyclopedia of integer sequences (2013) · Zbl 1274.11001 |
| [15] | Steingrímsson, Einar, Some Open Problems on Permutation Patterns, London Mathematical Society Lecture Note Series, 239-263 (2013) · Zbl 1300.05020 |
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.
