Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes
From MaRDI portal
Abstract: One of the most challenging problems in enumerative combinatorics is to count Wilf classes, where you are given a pattern, or set of patterns, and you are asked to find a "formula", or at least an efficient algorithm, that inputs a positive integer n and outputs the number of permutations avoiding that pattern. In 1996, John Noonan and Doron Zeilberger initiated the counting of permutations that have a prescribed, r, say, occurrences of a given pattern. They gave an ingenious method to generate Functional Equations, alas, with an unbounded number of "catalytic variables", but then described a clever way, using multivariable calculus, how to get enumeration schemes. Alas, their method becomes very complicated for r larger than 1. In the present article we describe a far simpler way to squeeze the necessary information, in polynomial time, for increasing patterns of any length, and for any number of occurrences, r.
Recommendations
- Approaches for enumerating permutations with a prescribed number of occurrences of patterns
- Using functional equations to enumerate 1324-avoiding permutations
- Enumeration Schemes for Restricted Permutations
- Enumeration schemes for vincular patterns
- Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns
Cited in
(8)- Enumeration schemes and, more importantly, their automatic generation
- Automatic generation of theorems and proofs on enumerating consecutive-Wilf classes
- Approaches for enumerating permutations with a prescribed number of occurrences of patterns
- Using functional equations to enumerate 1324-avoiding permutations
- Enumeration Schemes for Restricted Permutations
- An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences
- Counting permutations where the difference between entries located r places apart can never be s (for any given positive integers r and s)
- Counting occurrences of patterns in permutations
Describes a project that uses
Uses Software
This page was built for publication: Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1940420)
