Portal de Periódicos da CAPES

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

1090-2074

Brian Nakamura, Doron Zeilberger,

History and advancements in chemistry

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, 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.