A350250 Numbers k such that the k-th composition in standard order is a non-alternating permutation of an initial interval of positive integers.

37, 52, 549, 550, 556, 564, 581, 600, 616, 649, 657, 712, 786, 802, 836, 840, 16933, 16934, 16937, 16940, 16946, 16948, 16965, 16977, 16984, 16994, 17000, 17033, 17041, 17092, 17096, 17170, 17186, 17220, 17224, 17445, 17446, 17452, 17460, 17541, 17569, 17584

Offset: 1

Author

Gus Wiseman, Jan 13 2022

Keywords

• nonn

Comments

A sequence is alternating if it is alternately strictly increasing and strictly decreasing, starting with either.

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.

Examples

			The terms and corresponding permutations begin:
     37: (3,2,1)
     52: (1,2,3)
    549: (4,3,2,1)
    550: (4,3,1,2)
    556: (4,2,1,3)
    564: (4,1,2,3)
    581: (3,4,2,1)
    600: (3,2,1,4)
    616: (3,1,2,4)
    649: (2,4,3,1)
    657: (2,3,4,1)
    712: (2,1,3,4)
    786: (1,4,3,2)
    802: (1,3,4,2)
    836: (1,2,4,3)
    840: (1,2,3,4)
  16933: (5,4,3,2,1)
		

Crossrefs

This is the non-alternating case of A333218.

This is the restriction of A345168 to permutations, complement A345167.

These partitions are counted by A348615, complement A001250.

A003242 counts anti-run compositions, patterns A005649.

A025047 counts alternating compositions, directed A025048/A025049.

A345192 counts non-alternating compositions.

A345194 counts alternating patterns, complement A350252.

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:

- Weakly decreasing compositions (partitions) are A114994, strict A333256.

- Weakly increasing compositions (multisets) are A225620, strict A333255.

- Strict compositions are A233564.

- Constant compositions are A272919.

- Anti-run compositions are A333489, complement A348612.

Cf. A008965, A059893, A164894, A246534, A333217, A344605, A345162, A350251, A345163, A345171, A345172, 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];
Select[Range[0,1000],(Sort[stc[#]]==Range[Length[stc[#]]]&&!wigQ[stc[#]])&]