login
The a(n)-th composition in standard order is the sequence of run-lengths of the n-th composition in standard order.
60

%I #10 Mar 31 2020 10:54:13

%S 0,1,1,2,1,3,3,4,1,3,2,6,3,7,5,8,1,3,3,6,3,5,7,12,3,7,6,14,5,11,9,16,

%T 1,3,3,6,2,7,7,12,3,7,4,10,7,15,13,24,3,7,7,14,7,13,15,28,5,11,10,22,

%U 9,19,17,32,1,3,3,6,3,7,7,12,3,5,6,14,7,15,13

%N The a(n)-th composition in standard order is the sequence of run-lengths of the n-th composition in standard order.

%C A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of 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 Claude Lenormand, <a href="/A318921/a318921.pdf">Deux transformations sur les mots</a>, Preprint, 5 pages, Nov 17 2003.

%F A000120(n) = A070939(a(n)).

%F A000120(a(n)) = A124767(n).

%e The standard compositions and their run-lengths:

%e 0 ~ () -> () ~ 0

%e 1 ~ (1) -> (1) ~ 1

%e 2 ~ (2) -> (1) ~ 1

%e 3 ~ (11) -> (2) ~ 2

%e 4 ~ (3) -> (1) ~ 1

%e 5 ~ (21) -> (11) ~ 3

%e 6 ~ (12) -> (11) ~ 3

%e 7 ~ (111) -> (3) ~ 4

%e 8 ~ (4) -> (1) ~ 1

%e 9 ~ (31) -> (11) ~ 3

%e 10 ~ (22) -> (2) ~ 2

%e 11 ~ (211) -> (12) ~ 6

%e 12 ~ (13) -> (11) ~ 3

%e 13 ~ (121) -> (111) ~ 7

%e 14 ~ (112) -> (21) ~ 5

%e 15 ~ (1111) -> (4) ~ 8

%e 16 ~ (5) -> (1) ~ 1

%e 17 ~ (41) -> (11) ~ 3

%e 18 ~ (32) -> (11) ~ 3

%e 19 ~ (311) -> (12) ~ 6

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

%t Table[Total[2^(Accumulate[Reverse[Length/@Split[stc[n]]]])]/2,{n,0,30}]

%Y Positions of first appearances are A333630.

%Y All of the following pertain to compositions in standard order (A066099):

%Y - The length is A000120.

%Y - The partial sums from the right are A048793.

%Y - The sum is A070939.

%Y - Adjacent equal pairs are counted by A124762.

%Y - Equal runs are counted by A124767.

%Y - Strict compositions are ranked by A233564.

%Y - The partial sums from the left are A272020.

%Y - Constant compositions are ranked by A272919.

%Y - Normal compositions are ranked by A333217.

%Y - Heinz number is A333219.

%Y - Anti-runs are counted by A333381.

%Y - Adjacent unequal pairs are counted by A333382.

%Y - Runs-resistance is A333628.

%Y - First appearances of run-resistances are A333629.

%Y Cf. A029931, A098504, A114994, A225620, A228351, A238279, A242882, A318928, A329744, A329747, A333489.

%K nonn

%O 0,4

%A _Gus Wiseman_, Mar 30 2020