A350356 - OEIS

%I #7 Jan 18 2022 05:57:11

%S 0,1,2,4,5,8,9,16,17,18,22,32,33,34,38,44,45,64,65,66,68,70,76,77,88,

%T 89,128,129,130,132,134,140,141,148,152,153,176,177,178,182,256,257,

%U 258,260,262,264,268,269,276,280,281,296,297,304,305,306,310,352,353

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

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

%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vTCPiJVFUXN8IqfLlCXkgP15yrGWeRhFS4ozST5oA4Bl2PYS-XTA3sGsAEXvwW-B0ealpD8qnoxFqN3/pub">Statistics, classes, and transformations of standard compositions</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Alternating_permutation">Alternating permutation</a>

%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    5: (2,1)

%e    8: (4)

%e    9: (3,1)

%e   16: (5)

%e   17: (4,1)

%e   18: (3,2)

%e   22: (2,1,2)

%e   32: (6)

%e   33: (5,1)

%e   34: (4,2)

%e   38: (3,1,2)

%e   44: (2,1,3)

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

%t doupQ[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],doupQ[stc[#]]&]

%Y The case of permutations is counted by A000111.

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

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

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

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

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

%Y Counting patterns of this type gives A350354.

%Y The up/down version is A350355.

%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