OFFSET
1,3
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).
LINKS
EXAMPLE
The sequence together with the corresponding compositions begins:
0: ()
1: (1)
5: (2,1)
6: (1,2)
38: (3,1,2)
41: (2,3,1)
44: (2,1,3)
50: (1,3,2)
553: (4,2,3,1)
562: (4,1,3,2)
582: (3,4,1,2)
593: (3,2,4,1)
610: (3,1,4,2)
652: (2,4,1,3)
664: (2,3,1,4)
708: (2,1,4,3)
788: (1,4,2,3)
808: (1,3,2,4)
16966: (5,3,4,1,2)
17036: (5,2,4,1,3)
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
Subset of A333218, which ranks permutations of initial intervals.
A003242 counts Carlitz (anti-run) compositions.
A345163 counts normal partitions with an alternating permutation.
A345164 counts alternating permutations of prime indices.
A345170 counts partitions with an alternating permutation.
Compositions in standard order are the rows of A066099:
- Heinz number is given by A333219.
- Runs-resistance is given by A333628.
- Carlitz (anti-run) compositions are ranked by A333489.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 08 2021
STATUS
approved