A306314 Number of length-n binary words w such that ww is rich.

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

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 length-n binary words w such that the infinite word www... is rich. And also the number of length-n binary words w that are products of two palindromes, where all the conjugates of w are rich.

Links

Table of n, a(n) for n=1..30.

A. Glen, J. Justin, S. Widmer, and L. Q. Zamboni, Palindromic richness, European J. Combinatorics 30 (2009), 510-531. 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=n-1))
    return sum(2 for w in binn if rich(w+w))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Jul 07 2022

Crossrefs

Cf. A216264.

Sequence in context: A226930 A326751 A297702 * A007055 A175951 A072207

Adjacent sequences: A306311 A306312 A306313 * A306315 A306316 A306317

Keyword

nonn,more

Author

Jeffrey Shallit, Feb 06 2019

Extensions

a(17)-a(30) from Lars Blomberg, Feb 13 2019

Status

approved