Counting words without non-decreasing subwords of fixed length

Abstract

In arXiv:2511.13287, we derived exact formulas for generating functions counting the number of $n$-ary words avoiding \textit{strictly} increasing subwords of length $k$, and provided applications in probability theory as well as the continuous limit as $n\to \infty$. We also conjectured several corresponding formulas for the case where the ``strictly'' requirement is dropped. In this paper, we prove those formulas.

10 pages