A389600 Run-compression sum (A373953) minus number of maximal runs in the n-th composition in standard order.

0, 0, 1, 0, 2, 1, 1, 0, 3, 2, 1, 1, 2, 1, 1, 0, 4, 3, 3, 2, 3, 1, 2, 1, 3, 2, 1, 1, 2, 1, 1, 0, 5, 4, 4, 3, 2, 3, 3, 2, 4, 3, 1, 1, 3, 2, 2, 1, 4, 3, 3, 2, 3, 1, 2, 1, 3, 2, 1, 1, 2, 1, 1, 0, 6, 5, 5, 4, 5, 4, 4, 3, 5, 2, 3, 3, 4, 3, 3, 2, 5, 4, 4, 3, 3, 1, 2

Offset

0,5

Comments

We define the run-compression of a sequence to be the anti-run obtained by reducing each run of repeated parts to a single part. Alternatively, we remove all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has run-compression (1,2,1).

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=0..86.

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

Formula

a(n) = A373953(n) - A124767(n).

Example

The 11th composition in standard order is (2,1,1), with run-compression (2,1) and maximal runs ((2),(1,1)), so a(11) = 3 - 2 = 1.

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Total[First/@Split[stc[n]]]-Length[Split[stc[n]]], {n, 0, 100}]

Crossrefs

Positions of 0 are A000225.

For partitions instead of compositions we have A066328 - A001221.

The subtracted part is A124767, counted by A238279 and A333755.

The pre-subtracted part is A373953, counted by A116861 or A116608.

A011782 counts compositions.

A066099 lists compositions in standard order.

A114901 counts compositions with no isolated parts.

A333489 ranks anti-runs, counted by A003242.

A373949 counts compositions by run-compression sum, dual version A373951.

All of the following pertain to compositions in standard order:

- Length is A000120.

- Sum is A070939.

- Constant compositions are A272919.

- Anti-runs are counted by A333381.

- Run-lengths are A333769 (triangle).

Cf. A029931, A037201, A106356, A228351, A238130, A238343, A333217, A333627, A373954, A389532.

Sequence in context: A285097 A279209 A087117 * A392370 A387907 A029340

Adjacent sequences: A389597 A389598 A389599 * A389601 A389602 A389603

Keyword

nonn

Author

Gus Wiseman, Oct 11 2025

Status

approved