OFFSET
0,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.
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
EXAMPLE
The standard compositions and their compressions and compression sums begin:
0: () --> () --> 0
1: (1) --> (1) --> 1
2: (2) --> (2) --> 2
3: (1,1) --> (1) --> 1
4: (3) --> (3) --> 3
5: (2,1) --> (2,1) --> 3
6: (1,2) --> (1,2) --> 3
7: (1,1,1) --> (1) --> 1
8: (4) --> (4) --> 4
9: (3,1) --> (3,1) --> 4
10: (2,2) --> (2) --> 2
11: (2,1,1) --> (2,1) --> 3
12: (1,3) --> (1,3) --> 4
13: (1,2,1) --> (1,2,1) --> 4
14: (1,1,2) --> (1,2) --> 3
15: (1,1,1,1) --> (1) --> 1
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Total[First/@Split[stc[n]]], {n, 0, 100}]
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 25 2024
STATUS
approved