TY - JOUR

T1 - Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes

AU - Nakamura, Brian

AU - Zeilberger, Doron

N1 - Funding Information:
✩ Supported in part by the USA National Science Foundation. * Corresponding author. E-mail addresses: bnaka@math.rutgers.edu (B. Nakamura), zeilberg@math.rutgers.edu (D. Zeilberger). URLs: http://www.math.rutgers.edu/~bnaka/ (B. Nakamura), http://www.math.rutgers.edu/~zeilberg/ (D. Zeilberger).

PY - 2013/3

Y1 - 2013/3

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

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

KW - Algorithm

KW - Exact enumeration

KW - Functional equations

KW - Permutation patterns

UR - http://www.scopus.com/inward/record.url?scp=84873107684&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84873107684&partnerID=8YFLogxK

U2 - 10.1016/j.aam.2012.10.003

DO - 10.1016/j.aam.2012.10.003

M3 - Article

AN - SCOPUS:84873107684

SN - 0196-8858

VL - 50

SP - 356

EP - 366

JO - Advances in Applied Mathematics

JF - Advances in Applied Mathematics

IS - 3

ER -