

A306314


Number of lengthn binary words w such that ww is rich.


0



2, 4, 8, 16, 32, 52, 100, 160, 260, 424, 684, 988, 1588, 2342, 3458, 5072, 7516, 10546, 15506, 21496, 30682, 42508, 60170, 81316, 114182, 153768, 212966, 283502, 390168, 513652
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

A rich word w is one that contains, as contiguous subwords, exactly n nonempty palindromes, where n is the length of w. An infinite word is rich if all of its (contiguous) subwords are rich. By a theorem of Glen, Justin, Widmer, and Zamboni (below), a(n) is also the number of lengthn binary words w such that the infinite word www... is rich. And also the number of lengthn binary words w that are products of two palindromes, where all the conjugates of w are rich.


LINKS

A. Glen, J. Justin, S. Widmer, and L. Q. Zamboni, Palindromicrichness, European J. Combinatorics 30 (2009), 510531. See Theorem 3.1, p. 515.


PROG

(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):
binn = ("0"+"".join(b) for b in product("01", repeat=n1))
return sum(2 for w in binn if rich(w+w))


CROSSREFS



KEYWORD

nonn,more


AUTHOR



EXTENSIONS



STATUS

approved



