Journal of Combinatorics

Volume 6 (2015)

Number 1–2

On the asymptotic statistics of the number of occurrences of multiple permutation patterns

Pages: 117 – 143

DOI: https://dx.doi.org/10.4310/JOC.2015.v6.n1.a8

Authors

Svante Janson (Department of Mathematics,Uppsala University, Uppsala, Sweden)

Brian Nakamura (Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), Rutgers University, Piscataway, New Jersey, U.S.A.)

Doron Zeilberger (Department of Mathematics, Rutgers University, Piscataway, New Jersey, U.S.A.)

Abstract

We study statistical properties of the random variables $X_{\sigma} (\pi)$, the number of occurrences of the pattern $\sigma$ in the permutation $\pi$. We present two contrasting approaches to this problem: traditional probability theory and the “less traditional” computational approach. Through the perspective of the first approach, we prove that for any pair of patterns $\sigma$ and $\tau$, the random variables $X_{\sigma}$ and $X_{\tau}$ are jointly asymptotically normal (when the permutation is chosen from $S_n$). From the other perspective, we develop algorithms that can show asymptotic normality and joint asymptotic normality (up to a point) and derive explicit formulas for quite a few moments and mixed moments empirically, yet rigorously. The computational approach can also be extended to the case where permutations are drawn from a set of pattern avoiders to produce many empirical moments and mixed moments. This data suggests that some random variables are not asymptotically normal in this setting.

Keywords

permutation pattern, random permutation, joint asymptotic normality, mixed moments

Full Text (PDF format)

Published 20 March 2015