|
|
A373953
|
|
Sum of run-compression of the n-th integer composition in standard order.
|
|
40
|
|
|
0, 1, 2, 1, 3, 3, 3, 1, 4, 4, 2, 3, 4, 4, 3, 1, 5, 5, 5, 4, 5, 3, 5, 3, 5, 5, 3, 4, 4, 4, 3, 1, 6, 6, 6, 5, 3, 6, 6, 4, 6, 6, 2, 3, 6, 6, 5, 3, 6, 6, 6, 5, 6, 4, 6, 4, 5, 5, 3, 4, 4, 4, 3, 1, 7, 7, 7, 6, 7, 7, 7, 5, 7, 4, 5, 6, 7, 7, 6, 4, 7, 7, 7, 6, 5, 3, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
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
|
Counting partitions by this statistic gives A116861, by length A116608.
A037201 gives compression of first differences of primes, halved A373947.
A066099 lists the parts of all compositions in standard order.
A114901 counts compositions with no isolated parts.
A240085 counts compositions with no unique parts.
Cf. A106356, A124762, A238130, A238343, A272919, A285981, A333381, A333382, A333627, A373952, A373954.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|