Palindromic rich words and run-length encodings

Abstract

A length n word is (palindromic) rich if it contains the maximum possible number, which is n, of distinct non-empty palindromic factors. We prove both necessary and sufficient conditions for richness in terms of run-length encodings of words. Relating sufficient conditions to integer partitions, we prove a lower bound of order Cn, where C≈37.6, on the growth function of the language of binary rich words. From experimental study we suggest that this growth function actually grows more slowly than nn, which makes our lower bound quite reasonable. © 2016 Elsevier B.V.