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

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

Offset: 1

Author

Torsten.Sillke(AT)uni-bielefeld.de

Keywords

• nonn
• easy
• nice

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 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).

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. 95-113.
• T. Sillke, How many words have the same autocorrelation value?

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.

Programs

Maple

a:= proc(n) option remember; `if`(n=0, 1/2,
       2*a(n-1)-`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[n-1] - a[n/2], 2*a[n-1]]; Array[a, 40] (* Jean-Franç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 *)

PARI

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

Formula

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

a(n) = A342085(2^n). - Gus Wiseman, Mar 08 2021

Extensions

More terms from James Sellers.

Additional comments from Michael Somos, Jun 09 2000