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