login
Numbers k such that the k-th composition in standard order covers an initial interval of positive integers.
141

%I #13 Mar 17 2020 21:17:55

%S 0,1,3,5,6,7,11,13,14,15,21,22,23,26,27,29,30,31,37,38,41,43,44,45,46,

%T 47,50,52,53,54,55,58,59,61,62,63,75,77,78,83,85,86,87,89,90,91,92,93,

%U 94,95,101,102,105,106,107,108,109,110,111,114,116,117,118

%N Numbers k such that the k-th composition in standard order covers an initial interval of positive integers.

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

%e The sequence of terms together with the corresponding compositions begins:

%e 0: () 37: (3,2,1) 75: (3,2,1,1)

%e 1: (1) 38: (3,1,2) 77: (3,1,2,1)

%e 3: (1,1) 41: (2,3,1) 78: (3,1,1,2)

%e 5: (2,1) 43: (2,2,1,1) 83: (2,3,1,1)

%e 6: (1,2) 44: (2,1,3) 85: (2,2,2,1)

%e 7: (1,1,1) 45: (2,1,2,1) 86: (2,2,1,2)

%e 11: (2,1,1) 46: (2,1,1,2) 87: (2,2,1,1,1)

%e 13: (1,2,1) 47: (2,1,1,1,1) 89: (2,1,3,1)

%e 14: (1,1,2) 50: (1,3,2) 90: (2,1,2,2)

%e 15: (1,1,1,1) 52: (1,2,3) 91: (2,1,2,1,1)

%e 21: (2,2,1) 53: (1,2,2,1) 92: (2,1,1,3)

%e 22: (2,1,2) 54: (1,2,1,2) 93: (2,1,1,2,1)

%e 23: (2,1,1,1) 55: (1,2,1,1,1) 94: (2,1,1,1,2)

%e 26: (1,2,2) 58: (1,1,2,2) 95: (2,1,1,1,1,1)

%e 27: (1,2,1,1) 59: (1,1,2,1,1) 101: (1,3,2,1)

%e 29: (1,1,2,1) 61: (1,1,1,2,1) 102: (1,3,1,2)

%e 30: (1,1,1,2) 62: (1,1,1,1,2) 105: (1,2,3,1)

%e 31: (1,1,1,1,1) 63: (1,1,1,1,1,1) 106: (1,2,2,2)

%t normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];

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

%t Select[Range[0,100],normQ[stc[#]]&]

%Y Sequences covering an initial interval are counted by A000670.

%Y Composition in standard order are A066099.

%Y The case of strictly increasing initial intervals is A164894.

%Y The case of strictly decreasing initial intervals is A246534.

%Y The case of permutations is A333218.

%Y The weakly increasing version is A333379.

%Y The weakly decreasing version is A333380.

%Y Cf. A000120, A029931, A048793, A070939, A225620, A228351, A233564, A272919, A333219, A333220.

%K nonn

%O 1,3

%A _Gus Wiseman_, Mar 15 2020