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

Abstract

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\le i\le 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\ge 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\le i\le 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\le 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.