cp's OEIS Frontend

First differs from A345168 in lacking 37, corresponding to the composition (3,2,1).

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.

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)

A178472(n) is a lower bound for a(n). This bound is exact for n = 2..10 and 12, but falls behind thereafter.

a(0) = 1 vacuously for the empty composition. One could take a(1) = 0, on the theory that each composition is followed by infinitely many 0's, and thus the 1 is not relatively prime to its neighbor; but this definition seems simpler.

Also Heinz numbers of integer partitions with no adjacent parts having quotient > 2 (counted by A342094). The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions.

Except for any number of 1's, these partitions must be strict. The fully strict case is A328188.

Partitions with no consecutive pair of parts relatively prime are A328187, with strict case A328220.

These are finite sequences q of positive integers summing to n such that q(i) >= q(i+2) for all possible i.

The strict case (alternating parts are strictly decreasing) is A000041. Is there a bijective proof?

Yes. Construct a Ferrers diagram by placing odd parts horizontally and even parts vertically in a fishbone pattern. The resulting Ferrers diagram will be for an ordinary partition and the process is reversible. It does not appear that this method can be applied to give a formula for this sequence. - Andrew Howroyd, Mar 25 2021

These are finite sequences q of positive integers summing to n such that q(i) = q(i+2) for all possible i.