A389597 Standard composition numbers of integer compositions with all distinct first differences.

0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 16, 17, 18, 19, 20, 21, 22, 24, 25, 26, 27, 28, 29, 32, 33, 34, 35, 36, 38, 40, 41, 44, 46, 48, 49, 50, 51, 53, 56, 57, 64, 65, 66, 67, 68, 69, 70, 72, 73, 74, 76, 77, 78, 80, 81, 82, 83, 84, 86, 88, 89, 90, 92

Offset

1,3

Comments

The k-th composition in standard order (graded reverse-lexicographic, 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. This gives a bijective correspondence between nonnegative integers and integer compositions.

Links

Table of n, a(n) for n=1..67.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

Example

The 13th composition in standard order is (1,2,1), with first differences (1,-1), which are distinct, so 13 is in the sequence.
The terms together with corresponding standard compositions begin:
   0: ()
   1: (1)
   2: (2)
   3: (1,1)
   4: (3)
   5: (2,1)
   6: (1,2)
   8: (4)
   9: (3,1)
  10: (2,2)
  11: (2,1,1)
  12: (1,3)
  13: (1,2,1)
  14: (1,1,2)
  16: (5)
  17: (4,1)
  18: (3,2)
  19: (3,1,1)

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Select[Range[0, 100], UnsameQ@@Differences[stc[#]]&]

Crossrefs

For partitions we have A325368, counted by A325325 (strict A320347).

These compositions are counted by A325545, rest A303664.

The complement is A389598, counted by A389599.

For equal instead of distinct differences we have A389731, counted by A175342.

For 0-prepended first differences we have A389734, counted by A389601.

A011782 counts compositions.

A066099 lists compositions in standard order.

A333489 ranks anti-runs, counted by A003242.

A364465 counts subsets with distinct differences.

All of the following pertain to compositions in standard order:

- Length is A000120.

- Sum is A070939.

- Strict compositions are A233564.

- Constant compositions are A272919.

Cf. A001221, A029931, A124767, A130091, A228351, A240026, A242882, A318928, A325366, A333627, A333628.

Sequence in context: A059561 A037474 A292638 * A000378 A335513 A367906

Adjacent sequences: A389594 A389595 A389596 * A389598 A389599 A389600

Keyword

nonn

Author

Gus Wiseman, Oct 11 2025

Status

approved