Counting pairs of words according to the number of common rises, levels, and descents

A level (\(L\)) is an occurrence of two consecutive equal entries in a word \(w = w_1 w_2 \cdots\), while a rise (\(R\)) or descent (\(D\)) occurs when the right or left entry, respectively, is strictly larger. If \(u = u_1 u_2 \cdots u_n\) and \(v = v_1 v_2 \cdots v_n\) are \(k\)-ary words of the same given length and \(1 \leq i \leq n-1\), then there is, for example, an occurrence of \(LR\) at index \(i\) if \(u_i = u_{i+1}\) and \(v_i < v_{i+1}\), and likewise for the other possibilities. Similar terminology may be used when discussing ordered \(d\)-tuples of \(k\)-ary words of length \(n\) (the set of which we’ll often denote by \([k]^{nd}\)). In this paper, we consider the problem of enumerating the members of \([k]^{nd}\) according to the number of occurrences of the pattern \(\rho\), where \(d \geq 1\) and \(\rho\) is any word of length \(d\) in the alphabet \(\{L, R, D\}\). In particular, we find an explicit formula for the generating function counting the members of \([k]^{nd}\) according to the number of occurrences of the patterns \(\rho = L^i R^{d-i}\), \(0 \leq i \leq d\), which, by symmetry, is seen to solve the aforementioned problem in its entirety. We also provide simple formulas for the average number of occurrences of \(\rho\) within all the members of \([k]^{nd}\), providing both algebraic and combinatorial proofs. Finally, in the case \(d = 2\), we solve the problem above where we also allow for \textit{weak rises} (which we’ll denote by \(R_w\)), i.e., indices \(i\) such that \(w_i \leq w_{i+1}\) in \(w\). Enumerating the cases \(R_w R_w\) and \(R_w R_{uw}\) seems to be more difficult, and to do so, we combine the kernel method with the simultaneous use of several recurrences.