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

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, 89, 128, 129, 130, 132, 134, 140, 141, 148, 152, 153, 176, 177, 178, 182, 256, 257, 258, 260, 262, 264, 268, 269, 276, 280, 281, 296, 297, 304, 305, 306, 310, 352, 353

Offset: 1

Author

Gus Wiseman, Jan 15 2022

Keywords

• nonn

Comments

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.

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

Examples

			The terms together with the corresponding compositions begin:
   0: ()
   1: (1)
   2: (2)
   4: (3)
   5: (2,1)
   8: (4)
   9: (3,1)
  16: (5)
  17: (4,1)
  18: (3,2)
  22: (2,1,2)
  32: (6)
  33: (5,1)
  34: (4,2)
  38: (3,1,2)
  44: (2,1,3)
  45: (2,1,2,1)
		

Links

• Gus Wiseman, Statistics, classes, and transformations of standard compositions
• Wikipedia, Alternating permutation

Crossrefs

The case of permutations is counted by A000111.

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

The strict case is counted by A129838, undirected A349054.

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

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

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

Counting patterns of this type gives A350354.

The up/down version is A350355.

A001250 counts alternating permutations, complement A348615.

A003242 counts anti-run compositions.

A011782 counts compositions, unordered A000041.

A345192 counts non-alternating compositions, ranked by A345168.

A349052 counts weakly alternating compositions, complement A349053.

A349057 ranks non-weakly alternating compositions.

Statistics of standard compositions:

- Length is A000120.

- Sum is A070939.

- Heinz number is A333219.

- Number of maximal anti-runs is A333381.

- Number of distinct parts is A334028.

Classes of standard compositions:

- Partitions are A114994, strict A333256.

- Multisets are A225620, strict A333255.

- Strict compositions are A233564.

- Constant compositions are A272919.

- Patterns are A333217.

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

Programs

Mathematica

doupQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]y[[m+1]]],{m,1,Length[y]-1}];
stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],doupQ[stc[#]]&]

Formula

A345167 = A350355 \/ A350356.