Using Noonan–Zeilberger Functional Equations to enumerate (in polynomial time!) generalized Wilf classes
2012; Elsevier BV; Volume: 50; Issue: 3 Linguagem: Inglês
10.1016/j.aam.2012.10.003
ISSN1090-2074
AutoresBrian Nakamura, Doron Zeilberger,
Tópico(s)History and advancements in chemistry
ResumoOne 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, on 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.
Referência(s)