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