The $\mu$ pattern in words

In this paper, we study the distribution of the number of occurrences of the simplest frame pattern, called the $\mu$ pattern, in words. Given a word $w = w_1 \dots w_n \in { \{ 1, \dots , k \} }^n$, we say that a pair $\langle w_i, w_j \rangle$ matches the $\mu$ pattern if $i \lt j, \; w_i \lt w_j$, and there is no $i \lt k \lt j$ such that $w_i \leq w_k \leq w_j$. We say that $\langle w_i, w_j \rangle$ is a trivial $\mu$-match if $w_i +1 = w_j$ and is a nontrivial $\mu$-match if $w_i +1 \lt w_j$. The main goal of this paper is to study the joint distribution of the number of trivial and nontrivial $\mu$-matches in ${ \{ 1, \dots , k \} }^*$.

Full Text (PDF format)

Published 29 October 2014