|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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.
A353838 ranks partitions with all distinct run-sums, counted by A353837.
A353851 counts compositions with all equal run-sums, ranked by A353848.
A353852 ranks compositions with all distinct run-sums, counted by A353850.
A353860 counts collapsible compositions.
A353863 counts run-sum-complete partitions.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|