cp's OEIS Frontend

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 A353847 #11 May 31 2022 10:59:37
%S A353847 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 A353847 26,20,21,18,16,32,33,34,34,32,37,38,36,40,41,32,34,44,45,42,40,48,49,
%U A353847 50,50,52,49,54,52,40,41,40,42,36,37,34,32,64,65,66,66
%N 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.
%C A353847 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 A353847 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 A353847 Mathematics Stack Exchange, <a href="https://math.stackexchange.com/q/87559">What is a sequence run? (answered 2011-12-01)</a>
%e A353847 As a triangle:
%e A353847    0
%e A353847    1
%e A353847    2  2
%e A353847    4  5  6  4
%e A353847    8  9  8 10 12 13 10  8
%e A353847   16 17 18 18 20 17 22 20 24 25 24 26 20 21 18 16
%e A353847 These are the standard composition numbers of the following compositions (transposed):
%e A353847   ()  (1)  (2)  (3)    (4)      (5)
%e A353847            (2)  (2,1)  (3,1)    (4,1)
%e A353847                 (1,2)  (4)      (3,2)
%e A353847                 (3)    (2,2)    (3,2)
%e A353847                        (1,3)    (2,3)
%e A353847                        (1,2,1)  (4,1)
%e A353847                        (2,2)    (2,1,2)
%e A353847                        (4)      (2,3)
%e A353847                                 (1,4)
%e A353847                                 (1,3,1)
%e A353847                                 (1,4)
%e A353847                                 (1,2,2)
%e A353847                                 (2,3)
%e A353847                                 (2,2,1)
%e A353847                                 (3,2)
%e A353847                                 (5)
%t A353847 stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
%t A353847 stcinv[q_]:=Total[2^(Accumulate[Reverse[q]])]/2;
%t A353847 Table[stcinv[Total/@Split[stc[n]]],{n,0,100}]
%Y A353847 Standard compositions are listed by A066099.
%Y A353847 The version for partitions is A353832.
%Y A353847 The run-sums themselves are listed by A353932, with A353849 distinct terms.
%Y A353847 A005811 counts runs in binary expansion.
%Y A353847 A300273 ranks collapsible partitions, counted by A275870.
%Y A353847 A353838 ranks partitions with all distinct run-sums, counted by A353837.
%Y A353847 A353851 counts compositions with all equal run-sums, ranked by A353848.
%Y A353847 A353840-A353846 pertain to partition run-sum trajectory.
%Y A353847 A353852 ranks compositions with all distinct run-sums, counted by A353850.
%Y A353847 A353853-A353859 pertain to composition run-sum trajectory.
%Y A353847 A353860 counts collapsible compositions.
%Y A353847 A353863 counts run-sum-complete partitions.
%Y A353847 Cf. A003242. A175413, A181819, A238279, A274174, A333381, A333489, A333755, A353835, A353839, A353864.
%K A353847 nonn
%O A353847 0,3
%A A353847 _Gus Wiseman_, May 30 2022