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

Brian Nakamura, Doron Zeilberger

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)356-366
Number of pages11
JournalAdvances in Applied Mathematics
Volume50
Issue number3
DOIs
StatePublished - Mar 1 2013

All Science Journal Classification (ASJC) codes

  • Applied Mathematics

Keywords

  • Algorithm
  • Exact enumeration
  • Functional equations
  • Permutation patterns

Fingerprint Dive into the research topics of 'Using Noonan-Zeilberger functional equations to enumerate (in polynomial time!) generalized Wilf classes'. Together they form a unique fingerprint.

Cite this