A045690 - OEIS

%I #47 Jun 24 2021 20:02:09

%S 1,1,2,3,6,10,20,37,74,142,284,558,1116,2212,4424,8811,17622,35170,

%T 70340,140538,281076,561868,1123736,2246914,4493828,8986540,17973080,

%U 35943948,71887896,143771368,287542736,575076661,1150153322,2300289022,4600578044,9201120918

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

%C The number of binary strings sharing the same autocorrelations.

%C Appears to be row sums of A155092, beginning from a(2). - _Mats Granvik_, Jan 20 2009

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

%C From _Gus Wiseman_, Mar 08 2021: (Start)

%C This sequence counts each of the following essentially equivalent things:

%C 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:

%C   {1}  {2}  {3}    {4}      {5}        {6}

%C             {2,3}  {3,4}    {3,5}      {4,6}

%C                    {2,3,4}  {4,5}      {5,6}

%C                             {2,3,5}    {3,4,6}

%C                             {3,4,5}    {3,5,6}

%C                             {2,3,4,5}  {4,5,6}

%C                                        {2,3,4,6}

%C                                        {2,3,5,6}

%C                                        {3,4,5,6}

%C                                        {2,3,4,5,6}

%C 2. For n > 1, sets of distinct positive integers with maximum n - 1 whose first-differences are term-wise less than their decapitation (remove the maximum). For example, the set q = {2,4,5} has first-differences (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 first-differences {1,2,1}, which are less than {2,3,5}, so r is counted under a(6).

%C 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:

%C   (1)  (2)  (3)   (4)    (5)     (6)

%C             (21)  (31)   (41)    (51)

%C                   (211)  (32)    (42)

%C                          (311)   (411)

%C                          (212)   (321)

%C                          (2111)  (312)

%C                                  (3111)

%C                                  (2121)

%C                                  (2112)

%C                                  (21111)

%C (End)

%H Alois P. Heinz, <a href="/A045690/b045690.txt">Table of n, a(n) for n = 1..3324</a> (first 500 terms from T. D. Noe)

%H E. H. Rivals, <a href="http://www.lirmm.fr/~rivals/RESEARCH/PERIOD/">Autocorrelation of Strings</a>.

%H E. H. Rivals, S. Rahmann <a href="http://www.lirmm.fr/~rivals/PUBLI/FILES/RivalsRahmannJCTA03.pdf">Combinatorics of Periods in Strings</a>

%H E. H. Rivals, S. Rahmann, <a href="http://dx.doi.org/10.1016/S0097-3165(03)00123-7">Combinatorics of Periods in Strings</a>, Journal of Combinatorial Theory - Series A, Vol. 104(1) (2003), pp. 95-113.

%H T. Sillke, <a href="http://www.mathematik.uni-bielefeld.de/~sillke/SEQUENCES/autocorrelation">How many words have the same autocorrelation value?</a>

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

%F a(n) = A342085(2^n). - _Gus Wiseman_, Mar 08 2021

%p a:= proc(n) option remember; `if`(n=0, 1/2,

%p        2*a(n-1)-`if`(n::odd, 0, a(n/2)))

%p     end:

%p seq(a(n), n=1..40);  # _Alois P. Heinz_, Jun 24 2021

%t 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 *)

%t Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&Min@@Divide@@@Partition[#,2,1]>1/2&]],{n,8}] (* _Gus Wiseman_, Mar 08 2021 *)

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

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

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

%Y The version with quotients <= 1/2 is A018819.

%Y The version with quotients < 1/2 is A040039.

%Y Multiplicative versions are A337135, A342083, A342084, A342085.

%Y A000045 counts sets containing n with all differences > 2.

%Y A000929 counts partitions with no adjacent parts having quotient < 2.

%Y A342094 counts partitions with no adjacent parts having quotient > 2.

%Y Cf. A003242, A038548, A056924, A154402, A167606, A342096, A342097, A342098, A342191.

%K nonn,easy,nice

%O 1,3

%A Torsten.Sillke(AT)uni-bielefeld.de

%E More terms from _James A. Sellers_.

%E Additional comments from _Michael Somos_, Jun 09 2000