Enumerating symmetric and non-symmetric peaks in words

Abstract

Let $[k]=\{1,2,\dots ,k\}$ be an alphabet over $k$ letters. A word $\omega$ of length $n$ over alphabet $[k]$ is an element of $[k{]}^n$ and is also called $k$-ary word of length $n$. We say that $\omega$ contains a peak, if exists $2\le i\le n-1$ such that ${\omega }_{i-1}{\omega }_{i+1}$. We say that $\omega$ contains a symmetric peak, if exists $2\le i\le n-1$ such that ${\omega }_{i-1}={\omega }_{i+1}<{\omega }_i$, and contains a non-symmetric peak, otherwise. In this paper, we find an explicit formula for the generating functions for the number of $k$-ary words of length $n$ according to the number of symmetric peaks and non-symmetric peaks in terms of Chebyshev polynomials of the second kind. Moreover, we find the number of symmetric and non-symmetric peaks in $k$-ary word of length $n$ in two ways by using generating functions techniques, and by applying probabilistic methods.