A389742 Number of integer compositions of n whose 0-prepended first differences are not all equal.

0, 0, 1, 2, 7, 15, 29, 63, 127, 254, 510, 1023, 2045, 4095, 8191, 16381, 32767, 65535, 131069, 262143, 524286, 1048573, 2097151, 4194303, 8388605, 16777215

Offset

0,4

Links

Table of n, a(n) for n=0..25.

Formula

a(n) = 2^(n-1) - A007862(n) for n > 0.

Example

The composition c = (1,2,3) has 0-prepended first differences (1,1,1), which are all equal, so c is not counted under a(6).
The a(0) = 0 through a(5) = 15 compositions:
  .  .  (1,1)  (2,1)    (1,3)      (1,4)
               (1,1,1)  (2,2)      (2,3)
                        (3,1)      (3,2)
                        (1,1,2)    (4,1)
                        (1,2,1)    (1,1,3)
                        (2,1,1)    (1,2,2)
                        (1,1,1,1)  (1,3,1)
                                   (2,1,2)
                                   (2,2,1)
                                   (3,1,1)
                                   (1,1,1,2)
                                   (1,1,2,1)
                                   (1,2,1,1)
                                   (2,1,1,1)
                                   (1,1,1,1,1)

Mathematica

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n], !SameQ@@Differences[Prepend[#, 0]]&]], {n, 0, 15}]

Crossrefs

The complement is counted by A007862, ranks A389732.

These compositions have ranks A389736.

The non 0-prepended version is A389741, ranks A389735.

For distinct instead of equal differences we have A389744, ranks A389738.

The complement for equal differences is A389601, ranks A389734.

A011782 counts compositions.

A066099 lists compositions in standard order.

A175342 counts arithmetic progressions, ranks A389731, subsets A051336.

A389743 counts compositions without distinct differences, ranks A389598.

A389811 counts partitions without equal differences, ranks A389812.

Cf. A000740, A008965, A049988, A059966, A070211, A124767, A325545, A325547, A325557, A332834, A389597.

Sequence in context: A289965 A290620 A290628 * A192962 A294539 A343531

Adjacent sequences: A389739 A389740 A389741 * A389743 A389744 A389745

Keyword

nonn,more

Author

Gus Wiseman, Oct 16 2025

Status

approved