## 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 language | English (US) |
---|---|

Pages (from-to) | 356-366 |

Number of pages | 11 |

Journal | Advances in Applied Mathematics |

Volume | 50 |

Issue number | 3 |

DOIs | |

State | Published - Mar 1 2013 |

## All Science Journal Classification (ASJC) codes

- Applied Mathematics

## Keywords

- Algorithm
- Exact enumeration
- Functional equations
- Permutation patterns