Automatic generation of theorems and proofs on enumerating consecutive-Wilf classes
From MaRDI portal
Abstract: This article, dedicated to Herbert Saul Wilf on the occaison of his forthcoming 80-th birthday, describes two complementary approaches to enumeration, the "positive" and the "negative", each with its advantages and disadvantages. Both approaches are amenable to automation, and when applied to the currently active subarea, initiated in 2003 by Sergi Elizalde and Marc Noy, of enumerating consecutive-Wilf classes (i.e. consecutive pattern-avoidance) in permutations, were successfully pursued by DZ's two current PhD students, Andrew Baxter and Brian Nakamura. The Maple packages SERGI and ELIZALDE, implementing the algorithms enable the computer to "do research" by deriving, "all by itself", functional equations for the generating functions that enable polynomial-time enumeration for any set of patterns. In the case of ELIZALDE (the "negative" approach), these functional equations can be sometimes (automatically!) simplified, and imply "explicit" formulas, that previously were derived by humans using ad-hoc methods. We also get lots of new "explicit" results, beyond the scope of humans, but we have to admit, that we still need humans to handle "infinite families" of patterns, but this too, no doubt, will soon be automatable, and we leave it as a challenge to the (human and/or computer) reader. The Maple packages, and lots of sample output, is available from the webpage of this article: http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html
Recommendations
- Enumeration Schemes for Restricted Permutations
- Enumeration schemes and, more importantly, their automatic generation
- Enumeration schemes for words avoiding permutations
- Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes
- Automatic discovery of structural rules of permutation classes
Cited in
(10)- Enumeration schemes and, more importantly, their automatic generation
- Clusters, generating functions and asymptotics for consecutive patterns in permutations
- Descent pattern avoidance
- Subregularity in infinitely labeled generating trees of restricted permutations
- Increasing consecutive patterns in words
- Automatic Theorem-Proving in Combinatorics on Words
- Automatic proofs for formulae enumerating proper polycubes
- A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences
- Enumeration Schemes for Restricted Permutations
- A new perspective on positivity in (consecutive) permutation patterns
Describes a project that uses
Uses Software
This page was built for publication: Automatic generation of theorems and proofs on enumerating consecutive-Wilf classes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2846957)
