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

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, 97, 98, 102, 108, 109, 128, 144, 145, 160, 161, 162, 166, 192, 193, 194, 196, 198, 204, 205, 216, 217, 256, 272, 288, 289, 290, 320, 321, 322, 324, 326, 332, 333, 384

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

Examples

			The terms together with the corresponding compositions begin:
   0: ()
   1: (1)
   2: (2)
   4: (3)
   6: (1,2)
   8: (4)
  12: (1,3)
  13: (1,2,1)
  16: (5)
  20: (2,3)
  24: (1,4)
  25: (1,3,1)
  32: (6)
  40: (2,4)
  41: (2,3,1)
  48: (1,5)
  49: (1,4,1)
  50: (1,3,2)
  54: (1,2,1,2)
		

Crossrefs

The case of permutations is counted by A000111.

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

The strict case is counted by A129838, undirected A349054.

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

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

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

Counting patterns of this type gives A350354.

The down/up version is A350356.

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

updoQ[y_]:=And@@Table[If[EvenQ[m],y[[m]]>y[[m+1]],y[[m]]
				

Formula

A345167 = A350355 \/ A350356.