Generalized pattern frequency in large permutations (Q1953411)

Summary: 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 \textit{S. Elizalde} [Adv. Appl. Math. 36, No. 2, 138--155 (2006; Zbl 1089.05007)].