A226452 Number of closed binary words of length n.

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

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

Michael S. Branicky, Python program

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. 381-390. Available at arXiv, arXiv:1305.6395 [cs.FL], 2013-2014.

Gabriele Fici, Open and Closed Words, in Giovanni Pighizzini, ed., The Formal Language Theory Column, Bulletin of EATCS, 2017.

Daniel Gabric, Asymptotic bounds for the number of closed and privileged words, arXiv:2206.14273 [math.CO], 2022.

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
(Python) # see link for faster, bit-based version
from itertools import product
def closed(w): # w is a closed word
    if len(set(w)) <= 1: return True
    for l in range(1, len(w)):
        if w[:l] == w[-l:] and w[:l] not in w[1:-1]:
            return True
    return False
def a(n):
    if n == 0: return 1
    return 2*sum(closed("0"+"".join(b)) for b in product("01", repeat=n-1))
print([a(n) for n in range(22)]) # Michael S. Branicky, Jul 09 2022

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