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

Author

Jeffrey Shallit, Mar 15 2013

Keywords

• nonn

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.

Examples

			For n = 8 we have a(n) = 2^8 - 4 = 252 because the only non-rich words are 00101100, 00110100, and their complements.
		

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.

Crossrefs

Cf. A225681.

Programs

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 *)

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

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