OFFSET
0,6
COMMENTS
Every sequence can be uniquely split into a sequence of non-overlapping runs. For example, the runs of (2,2,1,1,1,3,2,2) are ((2,2),(1,1,1),(3),(2,2)), with sums (4,3,3,4).
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
Mathematics Stack Exchange, What is a sequence run? (answered 2011-12-01)
EXAMPLE
Composition 462903 in standard order is (1,1,4,7,1,2,1,1,1), with run-sums (2,4,7,1,2,3), of which a(462903) = 5 are distinct.
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Table[Length[Union[Total/@Split[stc[n]]]], {n, 0, 100}]
CROSSREFS
Counting repeated runs also gives A124767.
Positions of first appearances are A246534.
For distinct run-lengths instead of run-sums we have A354579.
A005811 counts runs in binary expansion.
A066099 lists compositions in standard order.
A165413 counts distinct run-lengths in binary expansion.
A353847 represents the run-sum transformation for compositions.
Selected statistics of standard compositions:
- Length is A000120.
- Sum is A070939.
- Heinz number is A333219.
- Number of distinct parts is A334028.
Selected classes of standard compositions:
- Strict compositions are A233564.
- Constant compositions are A272919.
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 30 2022
STATUS
approved