|
%I #68 Jul 09 2022 12:14:43
%S 1,2,4,8,16,32,64,128,252,488,932,1756,3246,5916,10618,18800,32846,
%T 56704,96702,163184,272460,450586,738274,1199376,1932338,3089518,
%U 4903164,7728120,12099440,18825066,29112876,44767202,68461866,104153666,157657852,237510110,356158688
%N Number of rich binary words of length n.
%C 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.
%H Mikhail Rubinchik, <a href="/A216264/b216264.txt">Table of n, a(n) for n = 0..60</a>
%H Amy Glen, Jacques Justin, Steve Widmer and Luca Q. Zamboni, <a href="http://dx.doi.org/10.1016/j.ejc.2008.04.006">Palindromic richness</a>, European J. Combin. 30 (2009), no. 2, 510-531.
%H Chuan Guo, J. Shallit, A. M. Shur, <a href="http://arxiv.org/abs/1503.09112">On the Combinatorics of Palindromes and Antipalindromes</a>, arXiv preprint arXiv:1503.09112 [cs.FL], 2015.
%H Chuan Guo, J. Shallit, and A. M. Shur, <a href="https://doi.org/10.1016/j.ipl.2016.07.001">Palindromic Rich Words and Run-Length Encodings</a>, Information Processing Letters Volume 116, Issue 12, December 2016, Pages 735-738.
%H M. Rubinchik and A. M. Shur, <a href="http://arxiv.org/abs/1506.04862">Eertree: An Efficient Data Structure for Processing Palindromes in Strings</a>, arXiv preprint arXiv:1506.04862 [cs.DS], 2015.
%H Mikhail Rubinchik, <a href="http://pastebin.com/7KhcrE69">C program</a>.
%H Josef Rukavicka, <a href="https://arxiv.org/abs/1701.07778">On Number of Rich Words</a>, arXiv:1701.07778 [math.CO], 2016.
%H Josef Rukavicka, <a href="https://arxiv.org/abs/1810.03573">An Upper Bound for Palindromic and Factor Complexity of Rich Words</a>, arXiv:1810.03573 [math.CO], 2018.
%e For n = 8 we have a(n) = 2^8 - 4 = 252 because the only non-rich words are 00101100, 00110100, and their complements.
%t (* Program not suitable to compute a large number of terms *)
%t richQ[w_] := (w[[#[[1]] ;; #[[2]]]]& /@ SequencePosition[w, _?PalindromeQ] // Union // Length) == n+1;
%t 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 *)
%o (PARI) ispal(v) = {for (i=1, #v\2, if (v[i] != v[#v-i+1], return(0)); ); return(1); };
%o 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); }
%o 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
%o (Python)
%o from itertools import product
%o def pal(w): return w == w[::-1]
%o def rich(w):
%o subs = (w[i:j] for i in range(len(w)) for j in range(i+1, len(w)+1))
%o return len(w) == sum(pal(s) for s in set(subs))
%o def a(n):
%o if n == 0: return 1
%o return sum(2 for b in product("01", repeat=n-1) if rich("0"+"".join(b)))
%o print([a(n) for n in range(16)]) # _Michael S. Branicky_, Jul 07 2022
%Y Cf. A225681.
%K nonn
%O 0,2
%A _Jeffrey Shallit_, Mar 15 2013
%E a(17) from _Alois P. Heinz_, Mar 15 2013
%E a(18)-a(25) from _Jeffrey Shallit_, Mar 19 2013
%E a(26)-a(60) from _Mikhail Rubinchik_, Mar 05 2015
|
