login
Numbers k such that the k-th composition in standard order (row k of A066099) has weakly decreasing non-adjacent parts.
3

%I #10 May 25 2020 08:35:12

%S 0,1,2,3,4,5,6,7,8,9,10,11,12,13,15,16,17,18,19,20,21,22,23,24,25,27,

%T 31,32,33,34,35,36,37,38,39,40,41,42,43,45,47,48,49,51,55,63,64,65,66,

%U 67,68,69,70,71,72,73,74,75,76,77,79,80,81,82,83,85,86,87

%N Numbers k such that the k-th composition in standard order (row k of A066099) has weakly decreasing non-adjacent parts.

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

%C The complement starts: 14, 26, 28, 29, 30, 44, 46, 50, ...

%e The sequence together with the corresponding compositions begins:

%e 0: () 17: (4,1) 37: (3,2,1)

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

%e 2: (2) 19: (3,1,1) 39: (3,1,1,1)

%e 3: (1,1) 20: (2,3) 40: (2,4)

%e 4: (3) 21: (2,2,1) 41: (2,3,1)

%e 5: (2,1) 22: (2,1,2) 42: (2,2,2)

%e 6: (1,2) 23: (2,1,1,1) 43: (2,2,1,1)

%e 7: (1,1,1) 24: (1,4) 45: (2,1,2,1)

%e 8: (4) 25: (1,3,1) 47: (2,1,1,1,1)

%e 9: (3,1) 27: (1,2,1,1) 48: (1,5)

%e 10: (2,2) 31: (1,1,1,1,1) 49: (1,4,1)

%e 11: (2,1,1) 32: (6) 51: (1,3,1,1)

%e 12: (1,3) 33: (5,1) 55: (1,2,1,1,1)

%e 13: (1,2,1) 34: (4,2) 63: (1,1,1,1,1,1)

%e 15: (1,1,1,1) 35: (4,1,1) 64: (7)

%e 16: (5) 36: (3,3) 65: (6,1)

%e For example, (2,3,1,2) is such a composition because the non-adjacent pairs are (2,1), (2,2), (3,2), all of which are weakly decreasing, so 166 is in the sequence

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

%t Select[Range[0,100],!MatchQ[stc[#],{___,x_,__,y_,___}/;y>x]&]

%Y The case of normal sequences appears to be A028859.

%Y Strict compositions are A032020.

%Y A version for ordered set partitions is A332872.

%Y These compositions are enumerated by A333148.

%Y The strict case is enumerated by A333150.

%Y Cf. A072706, A072707, A227038, A332834, A333193.

%K nonn

%O 1,3

%A _Gus Wiseman_, May 18 2020