2012/09/11 by Brian Nakamura, Doron Zeilberger, Nakamura, Brian +1
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1209.2353
12 pages; Accompanied by numerous Maple packages and many input and output files available from <A HREF="http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/Gwilf.html">this url</A>
arxiv created 2012/09/11 · arxiv updated 2012/09/12
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.