Generalized Pattern Frequency in Large Permutations

Joshua Cooper, Erik Lundberg, Brendan Nagle


In the study of permutations, generalized patterns extend classical patterns by adding the requirement that certain adjacent integers in a pattern must be adjacent in the permutation.

For any generalized pattern $\pi_0^*$ of length $k$ with $1 \leq b \leq k$ blocks, we prove that for all $\mu > 0$, there exists $0 < c =c(k, \mu) < 1$ so that whenever $n \geq n_0(k, \mu, c)$, all but $c^n n!$ many $\pi \in S_n$ admit $(1 \pm \mu) \tfrac{1}{k!}\tbinom{n}{b}$ occurrences of $\pi_0^*$.  Up to the choice of $c$, this result is best possible for all $\pi_0^*$ with $k \geq 2$.

We also give a lower bound on avoidance of the generalized pattern $12$-$34$, which answers a question of S. Elizalde (2006). 


generalized patterns; pattern avoidance; Azuma's inequality; Chernoff's inequality; Sharkovsky's Theorem

Full Text: PDF