OFFSET
0,2
COMMENTS
A word of length n is "rich" if it contains, as subwords, exactly n + 1 distinct palindromes (including the empty word). Here "subword" means contiguous subsequence of the word.
LINKS
Mikhail Rubinchik, Table of n, a(n) for n = 0..60
Amy Glen, Jacques Justin, Steve Widmer and Luca Q. Zamboni, Palindromic richness, European J. Combin. 30 (2009), no. 2, 510-531.
Chuan Guo, J. Shallit, A. M. Shur, On the Combinatorics of Palindromes and Antipalindromes, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
Chuan Guo, J. Shallit, and A. M. Shur, Palindromic Rich Words and Run-Length Encodings, Information Processing Letters Volume 116, Issue 12, December 2016, Pages 735-738.
M. Rubinchik and A. M. Shur, Eertree: An Efficient Data Structure for Processing Palindromes in Strings, arXiv preprint arXiv:1506.04862 [cs.DS], 2015.
Mikhail Rubinchik, C program.
Josef Rukavicka, On Number of Rich Words, arXiv:1701.07778 [math.CO], 2016.
Josef Rukavicka, An Upper Bound for Palindromic and Factor Complexity of Rich Words, arXiv:1810.03573 [math.CO], 2018.
EXAMPLE
For n = 8 we have a(n) = 2^8 - 4 = 252 because the only non-rich words are 00101100, 00110100, and their complements.
MATHEMATICA
(* Program not suitable to compute a large number of terms *)
richQ[w_] := (w[[#[[1]] ;; #[[2]]]]& /@ SequencePosition[w, _?PalindromeQ] // Union // Length) == n+1;
a[n_] := a[n] = Select[PadLeft[IntegerDigits[#, 2], n]& /@ Range[0, 2^n-1], richQ] // Length; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 16}] (* Jean-François Alcover, Sep 22 2018 *)
PROG
(PARI) ispal(v) = {for (i=1, #v\2, if (v[i] != v[#v-i+1], return(0)); ); return(1); };
isrich(vb, n) = {pals = Set(); for (i=1, #vb, for (len=1, #vb-i+1, subword = vector(len, x, vb[i+x-1]); if (ispal(subword), pals = setunion(pals, Set(Str(subword)) ); ); ); ); if (length(pals)==n, return(1)); return (0); }
a(n) = {nbr = 0; for (i=0, 2^n-1, vb = binary(i); while(length(vb) < n, vb = concat(0, vb); ); if (isrich(vb, n), nbr++); ); return (nbr); } \\ Michel Marcus, May 26 2013
(Python)
from itertools import product
def pal(w): return w == w[::-1]
def rich(w):
subs = (w[i:j] for i in range(len(w)) for j in range(i+1, len(w)+1))
return len(w) == sum(pal(s) for s in set(subs))
def a(n):
if n == 0: return 1
return sum(2 for b in product("01", repeat=n-1) if rich("0"+"".join(b)))
print([a(n) for n in range(16)]) # Michael S. Branicky, Jul 07 2022
CROSSREFS
KEYWORD
nonn
AUTHOR
Jeffrey Shallit, Mar 15 2013
EXTENSIONS
a(17) from Alois P. Heinz, Mar 15 2013
a(18)-a(25) from Jeffrey Shallit, Mar 19 2013
a(26)-a(60) from Mikhail Rubinchik, Mar 05 2015
STATUS
approved