|
%I #49 Jul 09 2022 12:14:53
%S 1,2,2,4,6,12,20,36,62,116,204,364,664,1220,2240,4132,7646,14244,
%T 26644,49984,94132,177788,336756,639720,1218228,2325048,4446776,
%U 8520928,16356260,31447436,60552616,116753948,225404486,435677408,843029104,1632918624,3165936640
%N Number of closed binary words of length n.
%C 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.
%C a(n+1) <= 2*a(n); for n > 1: a(n) <= A094536(n). - _Reinhard Zumkeller_, Jun 15 2013
%H Lars Blomberg, <a href="/A226452/b226452.txt">Table of n, a(n) for n = 0..38</a>
%H Michael S. Branicky, <a href="/A226452/a226452.py.txt">Python program</a>
%H G. Badkobeh, G. Fici, Z. Lipták, <a href="http://dx.doi.org/10.1007/978-3-319-15579-1_29">On the number of closed factors in a word</a>, in A.-H. Dediu et al., eds., LATA 2015, LNCS 8977, 2015, pp. 381-390. Available at <a href="http://arxiv.org/abs/1305.6395">arXiv</a>, arXiv:1305.6395 [cs.FL], 2013-2014.
%H Gabriele Fici, <a href="http://bulletin.eatcs.org/index.php/beatcs/article/viewFile/508/497">Open and Closed Words</a>, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.
%H Daniel Gabric, <a href="https://arxiv.org/abs/2206.14273">Asymptotic bounds for the number of closed and privileged words</a>, arXiv:2206.14273 [math.CO], 2022.
%e a(4) = 6 because the only closed binary words of length 4 are 0000, 0101, 0110, and their complements.
%o (Haskell)
%o import Data.List (inits, tails, isInfixOf)
%o a226452 n = a226452_list !! n
%o a226452_list = 1 : 2 : f [[0,0],[0,1],[1,0],[1,1]] where
%o f bss = sum (map h bss) : f ((map (0 :) bss) ++ (map (1 :) bss)) where
%o h bs = fromEnum $ or $ zipWith
%o (\xs ys -> xs == ys && not (xs `isInfixOf` (init $ tail bs)))
%o (init $ inits bs) (reverse $ tails $ tail bs)
%o -- _Reinhard Zumkeller_, Jun 15 2013
%o (Python) # see link for faster, bit-based version
%o from itertools import product
%o def closed(w): # w is a closed word
%o if len(set(w)) <= 1: return True
%o for l in range(1, len(w)):
%o if w[:l] == w[-l:] and w[:l] not in w[1:-1]:
%o return True
%o return False
%o def a(n):
%o if n == 0: return 1
%o return 2*sum(closed("0"+"".join(b)) for b in product("01", repeat=n-1))
%o print([a(n) for n in range(22)]) # _Michael S. Branicky_, Jul 09 2022
%Y Cf. A297183, A297184, A297185.
%K nonn
%O 0,2
%A _Jeffrey Shallit_, Jun 07 2013
%E a(17)-a(23) from _Reinhard Zumkeller_, Jun 15 2013
%E a(24)-a(36) from _Lars Blomberg_, Dec 28 2015
| 