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