Generalized Pattern Frequency in Large Permutations

Abstract

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