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]

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

• 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 alpha₄=3+o(1), alpha₆=15+o(1), and we give it to o(n³))
  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 q^{NumberOfOccurrencesOfThePattern123} (in other words, the polynomials of degree n(n-1)(n-2)/6 whose coefficient of q^r 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 Home Page