A353847 - OEIS

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.

%I #11 May 31 2022 10:59:37

%S 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,

%T 26,20,21,18,16,32,33,34,34,32,37,38,36,40,41,32,34,44,45,42,40,48,49,

%U 50,50,52,49,54,52,40,41,40,42,36,37,34,32,64,65,66,66

%N 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.

%C 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).

%C 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.

%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/q/87559">What is a sequence run? (answered 2011-12-01)</a>

%e As a triangle:

%e 0

%e 1

%e 2 2

%e 4 5 6 4

%e 8 9 8 10 12 13 10 8

%e 16 17 18 18 20 17 22 20 24 25 24 26 20 21 18 16

%e These are the standard composition numbers of the following compositions (transposed):

%e () (1) (2) (3) (4) (5)

%e (2) (2,1) (3,1) (4,1)

%e (1,2) (4) (3,2)

%e (3) (2,2) (3,2)

%e (1,3) (2,3)

%e (1,2,1) (4,1)

%e (2,2) (2,1,2)

%e (4) (2,3)

%e (1,4)

%e (1,3,1)

%e (1,4)

%e (1,2,2)

%e (2,3)

%e (2,2,1)

%e (3,2)

%e (5)

%t stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;

%t Table[stcinv[Total/@Split[stc[n]]],{n,0,100}]

%Y Standard compositions are listed by A066099.

%Y The version for partitions is A353832.

%Y The run-sums themselves are listed by A353932, with A353849 distinct terms.

%Y A005811 counts runs in binary expansion.

%Y A300273 ranks collapsible partitions, counted by A275870.

%Y A353838 ranks partitions with all distinct run-sums, counted by A353837.

%Y A353851 counts compositions with all equal run-sums, ranked by A353848.

%Y A353840-A353846 pertain to partition run-sum trajectory.

%Y A353852 ranks compositions with all distinct run-sums, counted by A353850.

%Y A353853-A353859 pertain to composition run-sum trajectory.

%Y A353860 counts collapsible compositions.

%Y A353863 counts run-sum-complete partitions.

%Y Cf. A003242. A175413, A181819, A238279, A274174, A333381, A333489, A333755, A353835, A353839, A353864.

%K nonn

%O 0,3

%A _Gus Wiseman_, May 30 2022