A345169 Numbers k such that the k-th composition in standard order is a non-alternating anti-run.

37, 52, 69, 101, 104, 105, 133, 137, 150, 165, 180, 197, 200, 208, 209, 210, 261, 265, 274, 278, 300, 301, 308, 325, 328, 357, 360, 361, 389, 393, 400, 401, 406, 416, 417, 418, 421, 422, 436, 517, 521, 529, 530, 534, 549, 550, 556, 557, 564, 581, 600, 601, 613

Offset: 1

Author

Gus Wiseman, Jun 15 2021

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 sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either. For example, the partition (3,2,2,2,1) has no alternating permutations, even though it does have the anti-run permutations (2,3,2,1,2) and (2,1,2,3,2).

An anti-run (separation or Carlitz composition) is a sequence with no adjacent equal parts.

Examples

			The sequence of terms together with their binary indices begins:
     37: (3,2,1)      210: (1,2,3,2)      400: (1,3,5)
     52: (1,2,3)      261: (6,2,1)        401: (1,3,4,1)
     69: (4,2,1)      265: (5,3,1)        406: (1,3,2,1,2)
    101: (1,3,2,1)    274: (4,3,2)        416: (1,2,6)
    104: (1,2,4)      278: (4,2,1,2)      417: (1,2,5,1)
    105: (1,2,3,1)    300: (3,2,1,3)      418: (1,2,4,2)
    133: (5,2,1)      301: (3,2,1,2,1)    421: (1,2,3,2,1)
    137: (4,3,1)      308: (3,1,2,3)      422: (1,2,3,1,2)
    150: (3,2,1,2)    325: (2,4,2,1)      436: (1,2,1,2,3)
    165: (2,3,2,1)    328: (2,3,4)        517: (7,2,1)
    180: (2,1,2,3)    357: (2,1,3,2,1)    521: (6,3,1)
    197: (1,4,2,1)    360: (2,1,2,4)      529: (5,4,1)
    200: (1,3,4)      361: (2,1,2,3,1)    530: (5,3,2)
    208: (1,2,5)      389: (1,5,2,1)      534: (5,2,1,2)
    209: (1,2,4,1)    393: (1,4,3,1)      549: (4,3,2,1)
		

Links

• Wikipedia, Alternating permutation

Crossrefs

A version counting partitions is A345166, ranked by A345173.

These compositions are counted by A345195.

A001250 counts alternating permutations, complement A348615.

A003242 counts anti-run compositions.

A005649 counts anti-run patterns.

A025047 counts alternating or wiggly compositions, also A025048, A025049.

A325534 counts separable partitions, ranked by A335433.

A325535 counts inseparable partitions, ranked by A335448.

A345164 counts alternating permutations of prime indices.

A345165 counts partitions w/o an alternating permutation, ranked by A345171.

A345170 counts partitions w/ an alternating permutation, ranked by A345172.

A345192 counts non-alternating compositions.

A345194 counts alternating patterns (with twins: A344605).

Statistics of standard compositions:

- Length is A000120.

- Constant runs are A124767.

- Heinz number is A333219.

- Anti-runs are A333381.

- Runs-resistance is A333628.

- Number of distinct parts is A334028.

- Non-anti-runs are A348612.

Classes of standard compositions:

- Weakly decreasing compositions (partitions) are A114994.

- Weakly increasing compositions (multisets) are A225620.

- Strict compositions are A233564.

- Constant compositions are A272919.

- Strictly increasing compositions (sets) are A333255.

- Strictly decreasing compositions (strict partitions) are A333256.

- Anti-runs are A333489.

- Alternating compositions are A345167.

- Non-Alternating compositions are A345168.

Cf. A001222, A008965, A238279, A344614, A344615, A344652, A344653, A344654, A345162, A345163, A345193, A348609, A348613.

Programs

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
wigQ[y_]:=Or[Length[y]==0,Length[Split[y]]== Length[y]&&Length[Split[Sign[Differences[y]]]]==Length[y]-1];
sepQ[y_]:=!MatchQ[y,{_,x_,x_,_}];
Select[Range[0,1000],sepQ[stc[#]]&&!wigQ[stc[#]]&]

Formula

Intersection of A345168 (non-alternating) and A333489 (anti-run).