OFFSET
0,3
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
As a triangle:
0
1
2 2
4 5 6 4
8 9 8 10 12 13 10 8
16 17 18 18 20 17 22 20 24 25 24 26 20 21 18 16
These are the standard composition numbers of the following compositions (transposed):
() (1) (2) (3) (4) (5)
(2) (2,1) (3,1) (4,1)
(1,2) (4) (3,2)
(3) (2,2) (3,2)
(1,3) (2,3)
(1,2,1) (4,1)
(2,2) (2,1,2)
(4) (2,3)
(1,4)
(1,3,1)
(1,4)
(1,2,2)
(2,3)
(2,2,1)
(3,2)
(5)
MATHEMATICA
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
Table[stcinv[Total/@Split[stc[n]]], {n, 0, 100}]
CROSSREFS
Standard compositions are listed by A066099.
The version for partitions is A353832.
A005811 counts runs in binary expansion.
A353860 counts collapsible compositions.
A353863 counts run-sum-complete partitions.
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 30 2022
STATUS
approved