OFFSET
0,2
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.
We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).
LINKS
FORMULA
a(n) = A335474(n) + 1.
EXAMPLE
The a(180) = 7 patterns are: (), (1), (1,2), (2,1), (1,2,3), (2,1,2), (2,1,2,3).
MATHEMATICA
stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n, 2]], 1], 0]]];
mstype[q_]:=q/.Table[Union[q][[i]]->i, {i, Length[Union[q]]}];
Table[Length[Union[mstype/@ReplaceList[stc[n], {___, s___, ___}:>{s}]]], {n, 0, 30}]
CROSSREFS
The non-contiguous version is A335454.
Summing over indices with binary length n gives A335457(n).
The nonempty version is A335474.
The n-th composition has A124771(n) distinct consecutive subsequences.
The n-th composition has A333257(n) distinct subsequence-sums.
The n-th composition has A334299(n) distinct subsequences.
Minimal avoided patterns are counted by A335465.
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 21 2020
STATUS
approved