A350355 - OEIS

%I #8 Jan 18 2022 05:56:58

%S 0,1,2,4,6,8,12,13,16,20,24,25,32,40,41,48,49,50,54,64,72,80,81,82,96,

%T 97,98,102,108,109,128,144,145,160,161,162,166,192,193,194,196,198,

%U 204,205,216,217,256,272,288,289,290,320,321,322,324,326,332,333,384

%N Numbers k such that the k-th composition in standard order is up/down.

%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 A composition is up/down if it is alternately strictly increasing and strictly decreasing, starting with an increase. For example, the partition (3,2,2,2,1) has no up/down permutations, even though it does have the anti-run permutation (2,3,2,1,2).

%F A345167 = A350355 \/ A350356.

%e The terms together with the corresponding compositions begin:

%e    0: ()

%e    1: (1)

%e    2: (2)

%e    4: (3)

%e    6: (1,2)

%e    8: (4)

%e   12: (1,3)

%e   13: (1,2,1)

%e   16: (5)

%e   20: (2,3)

%e   24: (1,4)

%e   25: (1,3,1)

%e   32: (6)

%e   40: (2,4)

%e   41: (2,3,1)

%e   48: (1,5)

%e   49: (1,4,1)

%e   50: (1,3,2)

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

%t updoQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]>y[[m+1]],y[[m]]<y[[m+1]]],{m,1,Length[y]-1}];

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

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

%Y The case of permutations is counted by A000111.

%Y These compositions are counted by A025048, down/up A025049.

%Y The strict case is counted by A129838, undirected A349054.

%Y The weak version is counted by A129852, down/up A129853.

%Y The version for anti-runs is A333489, a superset, complement A348612.

%Y This is the up/down case of A345167, counted by A025047.

%Y Counting patterns of this type gives A350354.

%Y The down/up version is A350356.

%Y A001250 counts alternating permutations, complement A348615.

%Y A003242 counts anti-run compositions.

%Y A011782 counts compositions, unordered A000041.

%Y A345192 counts non-alternating compositions, ranked by A345168.

%Y A349052 counts weakly alternating compositions, complement A349053.

%Y A349057 ranks non-weakly alternating compositions.

%Y Statistics of standard compositions:

%Y - Length is A000120.

%Y - Sum is A070939.

%Y - Heinz number is A333219.

%Y - Number of maximal anti-runs is A333381.

%Y - Number of distinct parts is A334028.

%Y Classes of standard compositions:

%Y - Partitions are A114994, strict A333256.

%Y - Multisets are A225620, strict A333255.

%Y - Strict compositions are A233564.

%Y - Constant compositions are A272919.

%Y - Patterns are A333217.

%Y Cf. A008965, A049774, A095684, A106356, A238279, A344604, A344614, A344615, A345169, A345170, A345172, A349051, A349799.

%K nonn

%O 1,3

%A _Gus Wiseman_, Jan 15 2022