login
Number of closed binary words of length n.
5

%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