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
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