Journal of Combinatorics

Volume 5 (2014)

Number 3

The $\mu$ pattern in words

Pages: 379 – 417

DOI: http://dx.doi.org/10.4310/JOC.2014.v5.n3.a6

Authors

Janine Lobue Tiefenbruck (Department of Mathematics, University of California at San Diego, La Jolla, Calif., U.S.A.)

Jeffrey Remmel (Department of Mathematics, University of California at San Diego, La Jolla, Calif., U.S.A.)

Abstract

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)