On the Asymptotic Statistics of The Number of Occurrences Of Multiple Permutation Patterns

On the Asymptotic Statistics of The Number of Occurrences Of Multiple Permutation Patterns
By Svante Janson, Brian Nakamura, and Doron Zeilberger
LaTeX source .pdf

[Appeared in Journal of Combinatorics, v. 6, 117-143]

Written: Dec. 13, 2013
The usual question, in the currently booming subsubsubset of mathematics called "permutation patterns" is to count the number of permutations that avoid one specific pattern, or a finite set of them, i.e. counting those that have `no sins'. Around 1996, John Noonan and Doron Zeilberger, inspired by the quote from 1 John 1:8

"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).

Maple Packages
Important: This article is accompanied by Maple packages

PDSn, a Maple package to compute the weight-enumerator of the set of permutations S_n according weights of the form
t^{NumberOfOccurrencesOfPattern(π)}
for all patterns of length 3, and some patterns of length 4, as well as for multiple patterns.

PDAV132 a Maple package to compute the weight-enumerator of the set of 132-avoiding permutations according weights of the form
t^{NumberOfOccurrencesOfPattern(π)}
for all patterns (up to trivial symmetry) of length 3 that make sense, and the length-4 pattern 1234.

PDAV123 a Maple package to compute the weight-enumerator of the set of 123-avoiding permutations according weights of the form
t^{NumberOfOccurrencesOfPattern(π)}
for all patterns (up to trivial symmetry) of length 3.

PDAV1234 a Maple package to compute the weight-enumerator of the set of 1234-avoiding permutations according weights of the form
t^{NumberOfOccurrencesOfPattern(π)}
for all patterns (up to trivial symmetry) of length 3, some pairs, and all of them.

TwoCrvs, a Maple package that rigorously derives lower moments out of the data produced by PDSn, and numerical moments for the rest of them.

Sample Input and Output for the General Symbolic Statistical Analysis Maple package TwoCrvs

If you want to see the list of lists of mixed-moments for the statistics #123 and #132
the input gives the output.

Here are pictures of the scaled distribution of the r.v. "number of occurrences of the pattern 123" in S₁₆ S₁₇ S₁₈ and for all n=10-18

You can see that they look pretty normal!

Here are pictures of the scaled distribution of the r.v. "number of occurrences of the pattern 132" in the set of n-permutations avoiding the pattern 123 for n=19 n=20 and for all n=10-20
You can see that they look pretty ABNORMAL!

Sample Input and Output for the Permutation Patterns Maple Packages

The input and output files for the the package PDSn and their statistical analysis

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}
for n from 1 to 13,
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 1234} s^{Number Of Occurrences of the Pattern 1243}
for n from 1 to 13,
the input yields the output

To see the FULL generating function according to ALL length-3 patterns, i.e. according to the weight
t₁^{Number Of Occurrences of the Pattern 123} t₂^{Number Of Occurrences of the Pattern 132} t₃^{Number Of Occurrences of the Pattern 213} t₄^{Number Of Occurrences of the Pattern 231} t₅^{Number Of Occurrences of the Pattern 312} t₆^{Number Of Occurrences of the Pattern 321}
for n from 1 to 10,
the input yields the output

The input and output files for the the package PDAV123
Here the `sample-space' is no longer the set of all n-permutations, but rather the set of 123-avoiding n-permutations .

To see the list of weight-enumerators of the set of 123-avoiding n-permutations according to the weight
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

To see the list of weight-enumerators of the set of 123-avoiding n-permutations according to the weight
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

To see the list of weight-enumerators of the set of 123-avoiding n-permutations according to the weight
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

The input and output files for the the package PDAV132
Here the `sample-space' is no longer the set of all n-permutations, but rather the set of 132-avoiding n-permutations .

To see the list of weight-enumerators of the set of 132-avoiding n-permutations according to the weight
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

To see the list of weight-enumerators of the set of 132-avoiding n-permutations according to the weight
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

To see the list of weight-enumerators of the set of 132-avoiding n-permutations according to the weight
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

To see the list of weight-enumerators of the set of 132-avoiding n-permutations according to the weight
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

To see the list of weight-enumerators of the set of 132-avoiding n-permutations according to the weight
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

The input and output files for the the package PDAV1234

To see the list of weight-enumerators of the set of 1234-avoiding 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 list of weight-enumerators of the set of 1234-avoiding 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 list of weight-enumerators of the set of 1234-avoiding n-permutations according to the weight
t^{Number Of Occurrences of the Pattern 312}
for n from 1 to 18,
the input yields the output

To see the list of weight-enumerators of the set of 1234-avoiding n-permutations according to the weight
t^{Number Of Occurrences of the Pattern 321}
for n from 1 to 18,
the input yields the output

To see the list of weight-enumerators of the set of 1234-avoiding 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 input yields the output

To see the list of weight-enumerators of the set of 1234-avoiding n-permutations according to the weight
r^{Number Of Occurrences of the Pattern 123} s^{Number Of Occurrences of the Pattern 321}
for n from 1 to 15,
the input yields the output

To see the FULL generating function of 1234-avoiding n-permutations according to ALL length-3 patterns, i.e. according to the weight
t₁^{Number Of Occurrences of the Pattern 123} t₂^{Number Of Occurrences of the Pattern 132} t₃^{Number Of Occurrences of the Pattern 213} t₄^{Number Of Occurrences of the Pattern 231} t₅^{Number Of Occurrences of the Pattern 312} t₆^{Number Of Occurrences of the Pattern 321}
for n from 1 to 10,
the input yields the output

Doron Zeilberger's List of Papers
Doron Zeilberger's Home Page