The \(\mu\) pattern in words (Q482280)

Let \(\pi=\pi_1\pi_2\cdots\pi_n\) be any \(k\)-ary word of length \(n\). We say that a pair \((\pi_i,\pi_j)\) matches the \(\mu\) pattern (or \(\mu\)-matches) if \(i<j\), \(\pi_i<\pi_j\) and there is no \(i<k<j\) such that \(\pi_i\leq \pi_k\leq pi_j\). In the case \(\pi_i+1=\pi_j\), the pair is called trivial, otherwise, the pair is called nontrivial. The aim of this paper is to study the generating function for the number of \(k\)-ary words of length \(n\) according to the number of trivial \(\mu\)-matches and the number of nontrivial \(\mu\)-matches. This has been done by using generating functions and weighted finite automaton techniques.