OFFSET
1,3
COMMENTS
Note we shorten the language, "the k-th composition in standard order," to "the standard composition of k."
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
EXAMPLE
The terms together with their standard compositions begin:
0: ()
1: (1)
2: (2)
3: (1,1)
4: (3)
6: (1,2)
7: (1,1,1)
8: (4)
9: (3,1)
10: (2,2)
12: (1,3)
14: (1,1,2)
15: (1,1,1,1)
18: (3,2)
19: (3,1,1)
24: (1,4)
25: (1,3,1)
26: (1,2,2)
For example, the 532,488-th composition is (6,10,4), with standard compositions ((1,2),(2,2),(3)), with weakly increasing concatenation (1,2,2,2,3), so 532,488 is in the sequence.
MATHEMATICA
stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Select[Range[0, 100], OrderedQ[Join@@stc/@stc[#]]&]
CROSSREFS
See link for sequences related to standard compositions.
Standard compositions are listed by A066099.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 10 2022
STATUS
approved