A334966 Numbers k such that the k-th composition in standard order (row k of A066099) has weakly decreasing non-adjacent parts.

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 47, 48, 49, 51, 55, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 85, 86, 87

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.

The complement starts: 14, 26, 28, 29, 30, 44, 46, 50, ...

Links

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

Example

The sequence together with the corresponding compositions begins:
   0: ()           17: (4,1)          37: (3,2,1)
   1: (1)          18: (3,2)          38: (3,1,2)
   2: (2)          19: (3,1,1)        39: (3,1,1,1)
   3: (1,1)        20: (2,3)          40: (2,4)
   4: (3)          21: (2,2,1)        41: (2,3,1)
   5: (2,1)        22: (2,1,2)        42: (2,2,2)
   6: (1,2)        23: (2,1,1,1)      43: (2,2,1,1)
   7: (1,1,1)      24: (1,4)          45: (2,1,2,1)
   8: (4)          25: (1,3,1)        47: (2,1,1,1,1)
   9: (3,1)        27: (1,2,1,1)      48: (1,5)
  10: (2,2)        31: (1,1,1,1,1)    49: (1,4,1)
  11: (2,1,1)      32: (6)            51: (1,3,1,1)
  12: (1,3)        33: (5,1)          55: (1,2,1,1,1)
  13: (1,2,1)      34: (4,2)          63: (1,1,1,1,1,1)
  15: (1,1,1,1)    35: (4,1,1)        64: (7)
  16: (5)          36: (3,3)          65: (6,1)
For example, (2,3,1,2) is such a composition because the non-adjacent pairs are (2,1), (2,2), (3,2), all of which are weakly decreasing, so 166 is in the sequence

Mathematica

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]//Reverse;
Select[Range[0, 100], !MatchQ[stc[#], {___, x_, __, y_, ___}/; y>x]&]

Crossrefs

The case of normal sequences appears to be A028859.

Strict compositions are A032020.

A version for ordered set partitions is A332872.

These compositions are enumerated by A333148.

The strict case is enumerated by A333150.

Cf. A072706, A072707, A227038, A332834, A333193.

Sequence in context: A023807 A023755 A335522 * A114886 A272477 A056651

Adjacent sequences: A334963 A334964 A334965 * A334967 A334968 A334969

Keyword

nonn

Author

Gus Wiseman, May 18 2020

Status

approved