Artigo Acesso aberto Revisado por pares

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

ISSN

1090-2074

Autores

Brian Nakamura, Doron Zeilberger,

Tópico(s)

History and advancements in chemistry

Resumo

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.

Referência(s)