A216264 Number of rich binary words of length n.

1, 2, 4, 8, 16, 32, 64, 128, 252, 488, 932, 1756, 3246, 5916, 10618, 18800, 32846, 56704, 96702, 163184, 272460, 450586, 738274, 1199376, 1932338, 3089518, 4903164, 7728120, 12099440, 18825066, 29112876, 44767202, 68461866, 104153666, 157657852, 237510110, 356158688

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

Cf. A225681.

Sequence in context: A306316 A275061 A230177 * A054045 A008860 A145114

Adjacent sequences: A216261 A216262 A216263 * A216265 A216266 A216267

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