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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A045690 Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton. 11
1, 1, 2, 3, 6, 10, 20, 37, 74, 142, 284, 558, 1116, 2212, 4424, 8811, 17622, 35170, 70340, 140538, 281076, 561868, 1123736, 2246914, 4493828, 8986540, 17973080, 35943948, 71887896, 143771368, 287542736, 575076661, 1150153322, 2300289022 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

The number of binary strings sharing the same autocorrelations.

Appears to be row sums of A155092, beginning from a(2). - Mats Granvik, Jan 20 2009

The number of binary words of length n (beginning with 0) which do not start with an even palindrome (i.e. which are not of the form ss*t where s is a (nonempty) word, s* is its reverse, and t is any (possibly empty) word). - Mamuka Jibladze, Sep 30 2014

LINKS

T. D. Noe, Table of n, a(n) for n = 1..500

E. H. Rivals, Autocorrelation of Strings.

E. H. Rivals, S. Rahmann Combinatorics of Periods in Strings

E. H. Rivals, S. Rahmann, Combinatorics of Periods in Strings, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113.

T. Sillke, How many words have the same autocorrelation value?

FORMULA

a(2n) = 2*a(2n-1) - a(n) for n >= 1; a(2n+1) = 2*a(2n) for n >= 1.

MATHEMATICA

a[1] = 1; a[n_] := a[n] = If[EvenQ[n], 2*a[n-1] - a[n/2], 2*a[n-1]]; Array[a, 40] (* Jean-Fran├žois Alcover, Jul 17 2015 *)

PROG

(PARI) a(n)=if(n<2, n>0, 2*a(n-1)-(1-n%2)*a(n\2))

CROSSREFS

Cf. A002083, A005434. A003000 = 2*a(n) for n > 0.

Different from, but easily confused with, A007148 and A093371.

Sequence in context: A008929 A164047 A158291 * A007148 A093371 A003214

Adjacent sequences:  A045687 A045688 A045689 * A045691 A045692 A045693

KEYWORD

nonn,easy,nice

AUTHOR

Torsten.Sillke(AT)uni-bielefeld.de

EXTENSIONS

More terms from James A. Sellers.

Additional comments from Michael Somos, Jun 09 2000

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 August 7 19:57 EDT 2020. Contains 336279 sequences. (Running on oeis4.)