

A045690


Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton.


28



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, 4600578044, 9201120918
(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
From Gus Wiseman, Mar 08 2021: (Start)
This sequence counts each of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n in which all adjacent elements have quotients > 1/2. For example, the a(1) = 1 through a(6) = 10 sets are:
{1} {2} {3} {4} {5} {6}
{2,3} {3,4} {3,5} {4,6}
{2,3,4} {4,5} {5,6}
{2,3,5} {3,4,6}
{3,4,5} {3,5,6}
{2,3,4,5} {4,5,6}
{2,3,4,6}
{2,3,5,6}
{3,4,5,6}
{2,3,4,5,6}
2. For n > 1, sets of distinct positive integers with maximum n  1 whose firstdifferences are termwise less than their decapitation (remove the maximum). For example, the set q = {2,4,5} has firstdifferences (2,1), which are not less than (2,4), so q is not counted under a(5). On the other hand, r = {2,3,5,6} has firstdifferences {1,2,1}, which are less than {2,3,5}, so r is counted under a(6).
3. Compositions of n where each part after the first is less than the sum of all preceding parts. For example, the a(1) = 1 through a(6) = 10 compositions are:
(1) (2) (3) (4) (5) (6)
(21) (31) (41) (51)
(211) (32) (42)
(311) (411)
(212) (321)
(2111) (312)
(3111)
(2121)
(2112)
(21111)
(End)


LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..3324 (first 500 terms from T. D. Noe)
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. 95113.
T. Sillke, How many words have the same autocorrelation value?


FORMULA

a(2n) = 2*a(2n1)  a(n) for n >= 1; a(2n+1) = 2*a(2n) for n >= 1.
a(n) = A342085(2^n).  Gus Wiseman, Mar 08 2021


MAPLE

a:= proc(n) option remember; `if`(n=0, 1/2,
2*a(n1)`if`(n::odd, 0, a(n/2)))
end:
seq(a(n), n=1..40); # Alois P. Heinz, Jun 24 2021


MATHEMATICA

a[1] = 1; a[n_] := a[n] = If[EvenQ[n], 2*a[n1]  a[n/2], 2*a[n1]]; Array[a, 40] (* JeanFrançois Alcover, Jul 17 2015 *)
Table[Length[Select[Subsets[Range[n]], MemberQ[#, n]&&Min@@Divide@@@Partition[#, 2, 1]>1/2&]], {n, 8}] (* Gus Wiseman, Mar 08 2021 *)


PROG

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


CROSSREFS

Cf. A002083, A005434. A003000 = 2*a(n) for n > 0.
Different from, but easily confused with, A007148 and A093371.
The version with quotients <= 1/2 is A018819.
The version with quotients < 1/2 is A040039.
Multiplicative versions are A337135, A342083, A342084, A342085.
A000045 counts sets containing n with all differences > 2.
A000929 counts partitions with no adjacent parts having quotient < 2.
A342094 counts partitions with no adjacent parts having quotient > 2.
Cf. A003242, A038548, A056924, A154402, A167606, A342096, A342097, A342098, A342191.
Sequence in context: A008929 A164047 A158291 * A007148 A093371 A339153
Adjacent sequences: A045687 A045688 A045689 * A045691 A045692 A045693


KEYWORD

nonn,easy,nice


AUTHOR

Torsten.Sillke(AT)unibielefeld.de


EXTENSIONS

More terms from James A. Sellers.
Additional comments from Michael Somos, Jun 09 2000


STATUS

approved



