Max Glass

math.CO — Combinatorics

On a counting conjecture for binary rich words

Contributed by Max Glass

Let $R_2(n)$ denote the number of binary rich words of length $n$. We prove that $\limsup_{n\to\infty}\frac{\log R_2(n)}{\sqrt{n}\log n}=\infty$. Consequently, $R_2(n)$ is not $O(n^{C\sqrt{n}})$ for any fixed $C>0$, disproving the conjectured upper bound $O((n/g(n))^{\sqrt{n}})$ with $g(n)\to\infty$. The proof combines independent permutation families through an ordered concatenation construction and a binary gap encoding.

Author comments: Formatting correction to the web abstract: repaired math delimiters and removed hard line breaks. The paper and mathematical results are unchanged. 4 pages. Lean 4 formalization and paper source: https://github.com/glasss13/rich-word-counting.