Using Noonan-Zeilberger Functional Equations to enumerate (in Polynomial Time!) Generalized Wilf classes

By Brian Nakamura and Doron Zeilberger


.pdf   .ps   .tex  
[Appeared in Advances in Applied Mathematics v. 50(2013), 356-366]
First Written: Sept. 7, 2012.

Last Update of both webpage and article: Oct. 9, 2012 [Thanks to Manuel Kauers, and an anonymous referee]

Previous update of this webpage (but not article): Sept. 28, 2012 [Thanks to Manuel Kauers]


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. Of course if the pattern is 12 then the answer is 1 (there is just one permutation avoiding the pattern 12, namely [n,n-1, ..., 1]). When the pattern is 123 the answer is famously the Catalan numbers (2n)!/(n!(n+1)!).

In a seminal article, John Noonan and Doron Zeilberger initiated the counting of permutations that have a prescribed, r, say, occurrences of a given pattern. When r=0 we are back to classical Wilf classes. 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. However, this method soon gets unwieldy, even for a computer, and in the present article we present an alternative, much easier to implement, and more efficient way, for getting the answer in Herb Wilf's sense, i.e. devising a "polynomial time algorithm" for computing the enumerating sequences for any r, and for many (but, of course, not all) patterns.


Maple Packages

Important: This article is accompanied by Maple packages

  • P123, to enumerate permutations containing exactly r occurrences of the pattern 123 for r=0,1,2,3, ...

  • F123, Also to enumerate permutations containing exactly r occurrences of the pattern 123 for r=0,1,2,3, ... but made more efficient for small r, and also shows an approach how to rigorously prove the "conjectured" expressions for the number of permutations with exactly r occurrences of the pattern 123 for r=1,2,3, [we only did it for r=1, but the approach could be used in general, but is it worth it?]

  • P1234, to enumerate permutations containing exactly r occurrences of the pattern 1234 for r=0,1,2,3, ...

  • F1234, Also to enumerate permutations containing exactly r occurrences of the pattern 1234 for r=0,1,2,3, ... but made more efficient for small r,

    Added Sept. 28, 2012: Manuel Kauers met a $100 challenge of DZ to compute the first 100 terms of the case r=1, and found 200! This new-improved version of F1234, contains procedure Seq1(); that outputs these 200 terms, as well as new procedures called Zinn and Easym to empricailly guess an aymptotic expression for the terms. Using the 200 terms it appears that the asymptotic is 9^n/n^4*C*(1+10/n+ ....) for C=1.40652..


  • P12345, to enumerate permutations containing exactly r occurrences of the pattern 12345 for r=0,1,2,3, ...

  • F12345, Also to enumerate permutations containing exactly r occurrences of the pattern 12345 for r=0,1,2,3, ... but made more efficient for small r,

  • P123456, to enumerate permutations containing exactly r occurrences of the pattern 123456 for r=0,1,2,3, ...

Sample Input and Output for the Maple package P123

  • Miklos Bona famously proved that the random variable "number of occurrences of pattern p", for any pattern p, is asymptotically normal. If you want to see this illustrated for the pattern 123, with explicit expressions for the average (this even you, lowly human, can do!, it is binomial(n,3)/6, of course), variance, as well as the third through the sixth moment-about-the-mean, as well as asympotic expressions, to order 2, for the so-called alpha coefficients, confirming Bona's theorem (for p=123 and the first six alpha coefficients, but with a vengeance, asymptotic normality only implies alpha4=3+o(1), alpha6=15+o(1), and we give it to o(n3))
    the input gives the output.

  • If you want to see the weight-enumerators of the symmetric groups of orders n=1 through n=20 according to the weight qNumberOfOccurrencesOfThePattern123 (in other words, the polynomials of degree n(n-1)(n-2)/6 whose coefficient of qr gives you the exact number of permutations of length n with exactly r occurrences of the pattern 123,
    the input gives the output.

  • If you want to see the first 25 terms for the sequence enumerating permutations with exactly r occurrences of the pattern 123, for r between 0 and 7 the
    the input gives the output.

  • If you want to see semi-rigorously derived explicit formulas, in n, for the number of permutations of length n with exactly r occurrences of the pattern 123, for r between 0 and 7, the
    the input gives the output.

Sample Input and Output for the Maple package P1234

  • If you want to see the first 50 terms for the sequences enumerating permutations with exactly r occurrences of the pattern 1234, for r=0 and r=1
    the input gives the output.

  • If you want to see the first 20 terms for the sequences enumerating permutations with exactly r occurrences of the pattern 1234, for r=0,r=1,r=2, and r=3, and r=4
    the input gives the output.

  • If you want to see the first 30 terms for the sequences enumerating permutations with exactly r occurrences of the pattern 1234, for r=0,r=1,r=2
    the input gives the output.

Sample Input and Output for the Maple package F1234

  • If you want to see the first 70 terms for the sequence enumerating permutations with exactly one occurrence of the pattern 1234, the input gives the output.
    Added Sept. 28, 2012: Manuel Kauers found 200 terms. He kindly gave us permission to post then here. He found them by using his C-code, that he also kindly allowed us to post.

Sample Input and Output for the Maple package P12345

  • If you want to see the first 20 terms for the sequence of permutations with exactly r occurrences of the pattern 12345, for r=0, r=1, and r=2,
    the input gives the output.

Sample Input and Output for the Maple package F12345

  • If you want to see the first 40 terms for the sequence enumerating permutations with exactly one occurrence of the pattern 12345, the input yields the output.

Sample Input and Output for the Maple package P123456

  • If you want to see the first 20 terms for the sequence of permutations with exactly r occurrences of the pattern 123456, for r=0, r=1, and r=2
    the input gives the output.

Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page