Palindromic rich words and run-length encodings

摘要

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 C-root n, where C approximate to 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 n(root n) which makes our lower bound quite reasonable. (C) 2016 Elsevier B.V. All rights reserved.