A373954 Excess run-compression of standard compositions. Sum of all parts minus sum of compressed parts of the n-th integer composition in standard order.

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

Offset

0,8

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.

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, compression removes all parts equal to the part immediately to their left. For example, (1,1,2,2,1) has compression (1,2,1).

Links

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

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

Formula

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

Example

The excess compression of (2,1,1,3) is 1, so a(92) = 1.

Mathematica

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

Crossrefs

For length instead of sum we have A124762, counted by A106356.

The opposite for length is A124767, counted by A238279 and A333755.

Positions of zeros are A333489, counted by A003242.

Positions of nonzeros are A348612, counted by A131044.

Compositions counted by this statistic are A373951, opposite A373949.

Compression of standard compositions is A373953.

Positions of ones are A373955.

A037201 gives compression of first differences of primes, halved A373947.

A066099 lists the parts of all compositions in standard order.

A114901 counts compositions with no isolated parts.

A116861 counts partitions by this statistic, by length A116608.

A240085 counts compositions with no unique parts.

A333627 takes the rank of a composition to the rank of its run-lengths.

Cf. A070939, A238130, A238343, A272919, A285981, A333213, A333381, A333382.

Sequence in context: A093693 A224447 A025436 * A170976 A134109 A325227

Adjacent sequences: A373951 A373952 A373953 * A373955 A373956 A373957

Keyword

nonn

Author

Gus Wiseman, Jun 27 2024

Status

approved