|
|
A045690
|
|
Number of binary words of length n (beginning with 0) whose autocorrelation function is the indicator of a singleton.
|
|
29
|
|
|
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.
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
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
|
|
|
FORMULA
|
a(2n) = 2*a(2n-1) - a(n) for n >= 1; a(2n+1) = 2*a(2n) for n >= 1.
|
|
MAPLE
|
a:= proc(n) option remember; `if`(n=0, 1/2,
2*a(n-1)-`if`(n::odd, 0, a(n/2)))
end:
|
|
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 *)
|
|
PROG
|
(PARI) a(n)=if(n<2, n>0, 2*a(n-1)-(1-n%2)*a(n\2))
|
|
CROSSREFS
|
The version with quotients <= 1/2 is A018819.
The version with quotients < 1/2 is A040039.
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.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
Torsten.Sillke(AT)uni-bielefeld.de
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|