

A226452


Number of closed binary words of length n.


4



1, 2, 2, 4, 6, 12, 20, 36, 62, 116, 204, 364, 664, 1220, 2240, 4132, 7646, 14244, 26644, 49984, 94132, 177788, 336756, 639720, 1218228, 2325048, 4446776, 8520928, 16356260, 31447436, 60552616, 116753948, 225404486, 435677408, 843029104, 1632918624, 3165936640
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


COMMENTS

A word is closed if it contains a proper factor that occurs both as a prefix and as a suffix but does not have internal occurrences.
a(n+1) <= 2*a(n); for n > 1: a(n) <= A094536(n).  Reinhard Zumkeller, Jun 15 2013


LINKS

Lars Blomberg, Table of n, a(n) for n = 0..38
G. Badkobeh, G. Fici, Z. Lipták, On the number of closed factors in a word, in A.H. Dediu et al., eds., LATA 2015, LNCS 8977, 2015, pp. 381390. Available at arXiv, arXiv:1305.6395 [cs.FL], 20132014.
Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.


EXAMPLE

a(4) = 6 because the only closed binary words of length 4 are 0000, 0101, 0110, and their complements.


PROG

(Haskell)
import Data.List (inits, tails, isInfixOf)
a226452 n = a226452_list !! n
a226452_list = 1 : 2 : f [[0, 0], [0, 1], [1, 0], [1, 1]] where
f bss = sum (map h bss) : f ((map (0 :) bss) ++ (map (1 :) bss)) where
h bs = fromEnum $ or $ zipWith
(\xs ys > xs == ys && not (xs `isInfixOf` (init $ tail bs)))
(init $ inits bs) (reverse $ tails $ tail bs)
 Reinhard Zumkeller, Jun 15 2013


CROSSREFS

Cf. A297183, A297184, A297185.
Sequence in context: A010101 A274942 A028408 * A037163 A059123 A001679
Adjacent sequences: A226449 A226450 A226451 * A226453 A226454 A226455


KEYWORD

nonn


AUTHOR

Jeffrey Shallit, Jun 07 2013


EXTENSIONS

a(17)a(23) from Reinhard Zumkeller, Jun 15 2013
a(24)a(36) from Lars Blomberg, Dec 28 2015


STATUS

approved



