Using functional equations to enumerate 1324-avoiding permutations

DOI10.1016/J.AAM.2014.01.006MaRDI QIDQ402577zbMATH OpenOpenAlexFDO

Authors Fredrik Johansson, Brian Nakamura

Publication date 28 August 2014

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1309.7117

zbMATH Keywords

functional equationspermutation patternsenumeration algorithm

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Functional equations and inequalities (39B99) Exact enumeration problems, generating functions (05A15)

Abstract: 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.

Recommendations

• Approaches for enumerating permutations with a prescribed number of occurrences of patterns
• On \(1324\)-avoiding permutations
• Three-letter-pattern avoiding permutations and functional equations
• Counting 1324-avoiding permutations
• 1324-avoiding permutations revisited

Cites work

• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• A new upper bound for 1324-avoiding permutations
• Approaches for enumerating permutations with a prescribed number of occurrences of patterns
• Asymptotic values for degrees associated with strips of Young diagrams
• Counting 1324-avoiding permutations
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• Excluded permutation matrices and the Stanley-Wilf conjecture
• On the Stanley--Wilf limit of 4231-avoiding permutations and a conjecture of Arratia
• On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
• Some open problems on permutation patterns
• Symmetric functions and P-recursiveness
• The On-Line Encyclopedia of Integer Sequences
• Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns
• Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes

Cited in

(12)

• The design of efficient dynamic programming and transfer matrix enumeration algorithms
• Generating permutations with restricted containers
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• On \(1324\)-avoiding permutations
• 1324-avoiding permutations revisited
• Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes
• On pattern avoiding indecomposable permutations
• On a family of conjectures of Joel Lewis on alternating permutations
• Three-letter-pattern avoiding permutations and functional equations
• Stieltjes moment sequences for pattern-avoiding permutations
• Approaches for enumerating permutations with a prescribed number of occurrences of patterns
• Permutations avoiding 1324 and patterns in Łukasiewicz paths

Describes a project that uses

Uses Software

• F12345
• P123456
• P12345
• P1234
• F1234
• F123
• P123
• OEIS

This page was built for publication: Using functional equations to enumerate 1324-avoiding permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q402577)