login
A353847
Composition run-sum transformation in terms of standard composition numbers. The a(k)-th composition in standard order is the sequence of run-sums of the k-th composition in standard order. Takes each index of a row of A066099 to the index of the row consisting of its run-sums.
54
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, 32, 33, 34, 34, 32, 37, 38, 36, 40, 41, 32, 34, 44, 45, 42, 40, 48, 49, 50, 50, 52, 49, 54, 52, 40, 41, 40, 42, 36, 37, 34, 32, 64, 65, 66, 66
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.
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.
The run-sums themselves are listed by A353932, with A353849 distinct terms.
A005811 counts runs in binary expansion.
A300273 ranks collapsible partitions, counted by A275870.
A353838 ranks partitions with all distinct run-sums, counted by A353837.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353840-A353846 pertain to partition run-sum trajectory.
A353852 ranks compositions with all distinct run-sums, counted by A353850.
A353853-A353859 pertain to composition run-sum trajectory.
A353860 counts collapsible compositions.
A353863 counts run-sum-complete partitions.
Sequence in context: A133937 A181523 A353855 * A181537 A130498 A263433
KEYWORD
nonn
AUTHOR
Gus Wiseman, May 30 2022
STATUS
approved