By Svante Janson, Brian Nakamura, and Doron Zeilberger
[Appeared in Journal of Combinatorics, v. 6, 117-143]
Written: Dec. 13, 2013
"If we say that we have no sin, we deceive ourselves, and the truth is not in us"
started the activity of counting permutations that have a few sins. But most permutations have many sins, and another interesting question is what is the average? (VERY easy, even for a human), variance? (intermediate for a human, very easy for a computer), and higher moments. In particular is it asymptotically normal? Standing on the shoulders of Svante Janson, Miklos Bona proved that this is the case for a single pattern. In this article, a beautiful example of a peaceful collaboration between two rival attitudes to mathematics, we (or rather the first named-author) show how to extend this result to proving that for any finite collection of patterns, the random variables, "number of occurrences of pattern", are joint asymptotically normal (but of course not independently so!), and we find the correlation matrix. so much for the human-conceptual approach.
On the computational side, using ample data, generated (taking many days!) by our beloved computers, and using very clever algorithms designed by Brian Nakamura, our same computers (in a few seconds!), using Doron Zeilberger's "Symbolic Moment Calculus", proved, in a completely elementary way, asymptotic normality, and joint asymptotic normality, up to a point, and confirmed this. It is possible that the functional equation approach could be used to give a fully elementary proof of the joint asymptotic normality, but we have better things to do. The advantage of the symbolic-computational approach is that it gives EXACT (not just asymptotic) explicit formulas for quite a few moments and mixed moments, all empirically (yet rigorously!, using the Zeilberger empirical-proof-is-often-also-rigorous philosophy).
t^{NumberOfOccurrencesOfPattern(π)}
for all patterns (up to trivial symmetry) of length 3, some pairs, and all of them.
You can see that they look pretty normal!
You can see that they look pretty ABNORMAL!
To see the list of weight-enumerators of the set of n-permutations according to the weight
t^{Number Of Occurrences of the Pattern 123}
for n from 1 to 18
the input
yields the
output
--------------------
To see the implication of this data set for computing the explicit moments and
semi-empirical evidence for asymptotic normality
the input
yields the
output
To see the list of weight-enumerators of the set of n-permutations according to the weight
t^{Number Of Occurrences of the Pattern 132}
for n from 1 to 18
the input
yields the
output
--------------------
To see the implication of this data set for computing the explicit moments and
semi-empirical evidence for asymptotic normality
the input
yields the
output
To see the list of weight-enumerators of the set of n-permutations according to the weight
t^{Number Of Occurrences of the Pattern 1234}
for n from 1 to 13, the
the input
yields the
output
--------------------
To see the implication of this data set for computing the explicit moments and
semi-empirical evidence for asymptotic normality
the input
yields the
output
To see the list of weight-enumerators of the set of n-permutations according to the weight
t^{Number Of Occurrences of the Pattern 1243}
for n from 1 to 13, the
the input
yields the
output
--------------------
To see the implication of this data set for computing the explicit moments and
semi-empirical evidence for asymptotic normality
the input
yields the
output
To see the list of weight-enumerators of the set of n-permutations according to the weight
r^{Number Of Occurrences of the Pattern 123} s^{Number Of Occurrences of the Pattern 132}
for n from 1 to 15, the
the input
yields the
output
--------------------
To see the implication of this data set for computing the explicit mixed moments and
semi-empirical evidence for joint-asymptotic normality
the input
yields the
output
To see the list of weight-enumerators of the set of n-permutations according to the weight
r^{Number Of Occurrences of the Pattern 123} s^{Number Of Occurrences of the Pattern 321}
To see the list of weight-enumerators of the set of n-permutations according to the weight
r^{Number Of Occurrences of the Pattern 1234} s^{Number Of Occurrences of the Pattern 1243}
To see the FULL generating function according to ALL length-3 patterns, i.e. according to the weight
t_{1}^{Number Of Occurrences of the Pattern 123} t_{2}^{Number Of Occurrences of the Pattern 132} t_{3}^{Number Of Occurrences of the Pattern 213} t_{4}^{Number Of Occurrences of the Pattern 231} t_{5}^{Number Of Occurrences of the Pattern 312} t_{6}^{Number Of Occurrences of the Pattern 321}
t^{Number Of Occurrences of the Pattern 132}
for n from 1 to 20,
the input
yields the
output
-----------------
To see a numerical analysis of this data set,
the input
yields
the output
t^{Number Of Occurrences of the Pattern 312}
for n from 1 to 20,
the input
yields the
output
output
-----------------
To see a numerical analysis of this data set,
the input
yields
the output
t^{Number Of Occurrences of the Pattern 321}
for n from 1 to 20,
the input
yields the
output
output
-----------------
To see a numerical analysis of this data set,
the input
yields
the output
t^{Number Of Occurrences of the Pattern 123}
for n from 1 to 20,
the input
yields the
output
-----------------
To see a numerical analysis of this data set,
the input
yields
the output
t^{Number Of Occurrences of the Pattern 213}
for n from 1 to 20,
the input
yields the
output
-----------------
To see a numerical analysis of this data set,
the input
yields
the output
t^{Number Of Occurrences of the Pattern 312}
for n from 1 to 20,
the input
yields the
output
-----------------
To see a numerical analysis of this data set,
the input
yields
the output
t^{Number Of Occurrences of the Pattern 321}
for n from 1 to 20,
the input
yields the
output
-----------------
To see a numerical analysis of this data set,
the input
yields
the output
t^{Number Of Occurrences of the Pattern 1234}
for n from 1 to 18,
the input
yields the
output
-----------------
To see a numerical analysis of this data set,
the input
yields
the output
t^{Number Of Occurrences of the Pattern 123}
for n from 1 to 18,
the input
yields the
output
t^{Number Of Occurrences of the Pattern 132}
for n from 1 to 18,
the input
yields the
output
t^{Number Of Occurrences of the Pattern 312}
for n from 1 to 18,
the input
yields the
output
t^{Number Of Occurrences of the Pattern 321}
for n from 1 to 18,
the input
yields the
output
r^{Number Of Occurrences of the Pattern 123} s^{Number Of Occurrences of the Pattern 132}
for n from 1 to 15,
the input
yields the
output
r^{Number Of Occurrences of the Pattern 123} s^{Number Of Occurrences of the Pattern 321}
To see the FULL generating function of 1234-avoiding n-permutations according to ALL length-3 patterns, i.e. according to the weight
t_{1}^{Number Of Occurrences of the Pattern 123} t_{2}^{Number Of Occurrences of the Pattern 132} t_{3}^{Number Of Occurrences of the Pattern 213} t_{4}^{Number Of Occurrences of the Pattern 231} t_{5}^{Number Of Occurrences of the Pattern 312} t_{6}^{Number Of Occurrences of the Pattern 321}