login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A216264 Number of rich binary words of length n. 5
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 1 05:25 EDT 2023. Contains 361673 sequences. (Running on oeis4.)