cp's OEIS Frontend

A226452 Number of closed binary words of length n.

%I A226452 #49 Jul 09 2022 12:14:53
%S A226452 1,2,2,4,6,12,20,36,62,116,204,364,664,1220,2240,4132,7646,14244,
%T A226452 26644,49984,94132,177788,336756,639720,1218228,2325048,4446776,
%U A226452 8520928,16356260,31447436,60552616,116753948,225404486,435677408,843029104,1632918624,3165936640
%N A226452 Number of closed binary words of length n.
%C A226452 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 A226452 a(n+1) <= 2*a(n); for n > 1: a(n) <= A094536(n). - _Reinhard Zumkeller_, Jun 15 2013
%H A226452 Lars Blomberg, <a href="/A226452/b226452.txt">Table of n, a(n) for n = 0..38</a>
%H A226452 Michael S. Branicky, <a href="/A226452/a226452.py.txt">Python program</a>
%H A226452 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 A226452 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 A226452 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 A226452 a(4) = 6 because the only closed binary words of length 4 are 0000, 0101, 0110, and their complements.
%o A226452 (Haskell)
%o A226452 import Data.List (inits, tails, isInfixOf)
%o A226452 a226452 n = a226452_list !! n
%o A226452 a226452_list = 1 : 2 : f [[0,0],[0,1],[1,0],[1,1]] where
%o A226452    f bss = sum (map h bss) : f ((map (0 :) bss) ++ (map (1 :) bss)) where
%o A226452    h bs = fromEnum $ or $ zipWith
%o A226452            (\xs ys -> xs == ys && not (xs `isInfixOf` (init $ tail bs)))
%o A226452            (init $ inits bs) (reverse $ tails $ tail bs)
%o A226452 -- _Reinhard Zumkeller_, Jun 15 2013
%o A226452 (Python) # see link for faster, bit-based version
%o A226452 from itertools import product
%o A226452 def closed(w): # w is a closed word
%o A226452     if len(set(w)) <= 1: return True
%o A226452     for l in range(1, len(w)):
%o A226452         if w[:l] == w[-l:] and w[:l] not in w[1:-1]:
%o A226452             return True
%o A226452     return False
%o A226452 def a(n):
%o A226452     if n == 0: return 1
%o A226452     return 2*sum(closed("0"+"".join(b)) for b in product("01", repeat=n-1))
%o A226452 print([a(n) for n in range(22)]) # _Michael S. Branicky_, Jul 09 2022
%Y A226452 Cf. A297183, A297184, A297185.
%K A226452 nonn
%O A226452 0,2
%A A226452 _Jeffrey Shallit_, Jun 07 2013
%E A226452 a(17)-a(23) from _Reinhard Zumkeller_, Jun 15 2013
%E A226452 a(24)-a(36) from _Lars Blomberg_, Dec 28 2015