login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A045691
Number of binary words of length n with autocorrelation function 2^(n-1)+1.
8
0, 1, 1, 3, 5, 11, 19, 41, 77, 159, 307, 625, 1231, 2481, 4921, 9883, 19689, 39455, 78751, 157661, 315015, 630337, 1260049, 2520723, 5040215, 10081661, 20160841, 40324163, 80643405, 161291731, 322573579, 645157041, 1290294393, 2580608475, 5161177495
OFFSET
0,4
COMMENTS
From Gus Wiseman, Jan 22 2022: (Start)
Also the number of subsets of {1..n} containing n but without adjacent elements of quotient 1/2. The Heinz numbers of these sets are a subset of the squarefree terms of A320340. For example, the a(1) = 1 through a(6) = 19 subsets are:
{1} {2} {3} {4} {5} {6}
{1,3} {1,4} {1,5} {1,6}
{2,3} {3,4} {2,5} {2,6}
{1,3,4} {3,5} {4,6}
{2,3,4} {4,5} {5,6}
{1,3,5} {1,4,6}
{1,4,5} {1,5,6}
{2,3,5} {2,5,6}
{3,4,5} {3,4,6}
{1,3,4,5} {3,5,6}
{2,3,4,5} {4,5,6}
{1,3,4,6}
{1,3,5,6}
{1,4,5,6}
{2,3,4,6}
{2,3,5,6}
{3,4,5,6}
{1,3,4,5,6}
{2,3,4,5,6}
(End)
FORMULA
a(2*n-1) = 2*a(2*n-2) - a(n) for n >= 2; a(2*n) = 2*a(2*n-1) + a(n) for n >= 2.
MATHEMATICA
Table[Length[Select[Subsets[Range[n]], MemberQ[#, n]&&And@@Table[#[[i-1]]/#[[i]]!=1/2, {i, 2, Length[#]}]&]], {n, 0, 15}] (* Gus Wiseman, Jan 22 2022 *)
CROSSREFS
If a(n) counts subsets of {1..n} with n and without adjacent quotients 1/2:
- The version with quotients <= 1/2 is A018819, partitions A000929.
- The version with quotients < 1/2 is A040039, partitions A342098.
- The version with quotients >= 1/2 is A045690(n+1), partitions A342094.
- The version with quotients > 1/2 is A045690, partitions A342096.
- Partitions of this type are counted by A350837, ranked by A350838.
- Strict partitions of this type are counted by A350840.
- For differences instead of quotients we have A350842, strict A350844.
- Partitions not of this type are counted by A350846, ranked by A350845.
A000740 = relatively prime subsets of {1..n} containing n.
A002843 = compositions with all adjacent quotients >= 1/2.
A050291 = double-free subsets of {1..n}.
A154402 = partitions with all adjacent quotients 2.
A308546 = double-closed subsets of {1..n}, with maximum: shifted right.
A323092 = double-free integer partitions, ranked by A320340, strict A120641.
A326115 = maximal double-free subsets of {1..n}.
Sequence in context: A089098 A129384 A131887 * A045961 A293820 A281380
KEYWORD
nonn
AUTHOR
Torsten Sillke (torsten.sillke(AT)lhsystems.com)
EXTENSIONS
More terms from Sean A. Irvine, Mar 18 2021
STATUS
approved