The paper is about counting sequences of symbols (called "words") that avoid certain forbidden patterns. Specifically, it focuses on words built from an alphabet of n symbols where no portion of the word forms a non-decreasing run of a fixed length k. A non-decreasing subword means a sequence of positions in the word where each symbol is the same as or larger than the one before it. For example, if k is 3, you want to count words that never contain three consecutive symbols where each is at least as big as the last.
This work is a follow-up to an earlier paper by the same authors, which solved the slightly simpler problem of avoiding strictly increasing subwords, meaning subwords where each symbol is strictly larger than the previous one (ties are allowed in that case). That earlier paper produced exact mathematical formulas for generating functions, which are algebraic tools that encode all the counts at once, and also explored connections to probability and what happens when the alphabet size grows very large. However, the analogous formulas for the non-decreasing case (where ties are forbidden in addition to drops) were only conjectured, not proven.
The main contribution of this paper is providing rigorous proofs of those conjectured formulas. Allowing ties in the forbidden pattern makes the combinatorial structure more complex, so new arguments were needed beyond those used in the strictly increasing case. The results give precise closed-form expressions for how many such words exist, which has implications for areas like probability theory and the study of random sequences, and the formulas also behave nicely in the limit where the alphabet becomes infinitely large.