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

Author

Jeffrey Shallit, Jun 07 2013

Keywords

• nonn

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

Examples

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

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.

Crossrefs

Cf. A297183, A297184, A297185.

Programs

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

Extensions

a(17)-a(23) from Reinhard Zumkeller, Jun 15 2013

a(24)-a(36) from Lars Blomberg, Dec 28 2015