login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A226452 Number of closed binary words of length n. 3
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 (list; graph; refs; listen; history; text; internal format)
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

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.

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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 21 22:55 EST 2020. Contains 331129 sequences. (Running on oeis4.)