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 Sn according weights of the form
tNumberOfOccurrencesOfPattern(π)
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
tNumberOfOccurrencesOfPattern(π)
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
tNumberOfOccurrencesOfPattern(π)
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

tNumberOfOccurrencesOfPattern(π)

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 S16   S17   S18 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

rNumber Of Occurrences of the Pattern 123 sNumber 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

rNumber Of Occurrences of the Pattern 123 sNumber 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

rNumber Of Occurrences of the Pattern 1234 sNumber 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

t1Number Of Occurrences of the Pattern 123 t2Number Of Occurrences of the Pattern 132 t3Number Of Occurrences of the Pattern 213 t4Number Of Occurrences of the Pattern 231 t5Number Of Occurrences of the Pattern 312 t6Number 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

tNumber 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

rNumber Of Occurrences of the Pattern 123 sNumber 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

rNumber Of Occurrences of the Pattern 123 sNumber 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

t1Number Of Occurrences of the Pattern 123 t2Number Of Occurrences of the Pattern 132 t3Number Of Occurrences of the Pattern 213 t4Number Of Occurrences of the Pattern 231 t5Number Of Occurrences of the Pattern 312 t6Number Of Occurrences of the Pattern 321

for n from 1 to 10,
the input yields the output

Doron Zeilberger's List of Papers