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,1

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.

Links

Table of n, a(n) for n=1..42.

Example

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)

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[#]])&]

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.

Sequence in context: A074401 A323476 A345169 * A092105 A101938 A060330

Adjacent sequences: A350247 A350248 A350249 * A350251 A350252 A350253

Keyword

nonn

Author

Gus Wiseman, Jan 13 2022

Status

approved