login
Numbers k such that the k-th composition in standard order (row k of A066099) has all equal run-sums.
33

%I #6 May 31 2022 11:38:54

%S 0,1,2,3,4,7,8,10,11,14,15,16,31,32,36,39,42,46,59,60,63,64,127,128,

%T 136,138,143,168,170,175,187,238,248,250,255,256,292,316,487,511,512,

%U 528,543,682,750,955,1008,1023,1024,2047,2048,2080,2084,2090,2111,2184

%N Numbers k such that the k-th composition in standard order (row k of A066099) has all equal run-sums.

%C Every sequence can be uniquely split into non-overlapping runs, read left-to-right. 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>

%F A353849(a(n)) = 1.

%e The terms together with their binary expansions and corresponding compositions begin:

%e 0: 0 ()

%e 1: 1 (1)

%e 2: 10 (2)

%e 3: 11 (1,1)

%e 4: 100 (3)

%e 7: 111 (1,1,1)

%e 8: 1000 (4)

%e 10: 1010 (2,2)

%e 11: 1011 (2,1,1)

%e 14: 1110 (1,1,2)

%e 15: 1111 (1,1,1,1)

%e 16: 10000 (5)

%e 31: 11111 (1,1,1,1,1)

%e 32: 100000 (6)

%e 36: 100100 (3,3)

%e 39: 100111 (3,1,1,1)

%e 42: 101010 (2,2,2)

%e 46: 101110 (2,1,1,2)

%e 59: 111011 (1,1,2,1,1)

%e 60: 111100 (1,1,1,3)

%e For example:

%e - The 59th composition in standard order is (1,1,2,1,1), with run-sums (2,2,2), so 59 is in the sequence.

%e - The 2298th composition in standard order is (4,1,1,1,1,2,2), with run-sums (4,4,4), so 2298 is in the sequence.

%e - The 2346th composition in standard order is (3,3,2,2,2), with run-sums (6,6), so 2346 is in the sequence.

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

%t Select[Range[0,100],SameQ@@Total/@Split[stc[#]]&]

%Y Standard compositions are listed by A066099.

%Y For equal lengths instead of sums we have A353744, counted by A329738.

%Y The version for partitions is A353833, counted by A304442.

%Y These compositions are counted by A353851.

%Y The distinct instead of equal version is A353852, counted by A353850.

%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 A351014 counts distinct runs in standard compositions, firsts A351015.

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

%Y A353847 represents the run-sum transformation for compositions.

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

%Y A353860 counts collapsible compositions.

%Y A353863 counts run-sum-complete partitions.

%Y Cf. A003242, A047966, A106356, A140690, A238279, A274174, A333381, A333489, A333755, A353832, A353864.

%K nonn

%O 0,3

%A _Gus Wiseman_, May 30 2022