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

 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.

Last modified September 23 14:51 EDT 2023. Contains 365551 sequences. (Running on oeis4.)