|
|
A335454
|
|
Number of normal patterns matched by the n-th composition in standard order (A066099).
|
|
48
|
|
|
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 5, 3, 6, 5, 5, 2, 3, 3, 5, 3, 5, 6, 7, 3, 6, 5, 9, 5, 9, 7, 6, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 4, 7, 5, 10, 9, 9, 3, 6, 5, 9, 4, 9, 10, 12, 5, 9, 7, 13, 7, 12, 9, 7, 2, 3, 3, 5, 3, 4, 5, 7, 3, 5, 5, 7, 6, 10, 9, 9, 3, 5, 6, 8, 5
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
We define a (normal) pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670. 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).
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 a(n) patterns for n = 0, 1, 3, 7, 11, 13, 23, 83, 27, 45:
0: 1: 11: 111: 211: 121: 2111: 2311: 1211: 2121:
---------------------------------------------------------------------
() () () () () () () () () ()
(1) (1) (1) (1) (1) (1) (1) (1) (1)
(11) (11) (11) (11) (11) (11) (11) (11)
(111) (21) (12) (21) (12) (12) (12)
(211) (21) (111) (21) (21) (21)
(121) (211) (211) (111) (121)
(2111) (231) (121) (211)
(2311) (211) (212)
(1211) (221)
(2121)
|
|
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/@Subsets[stc[n]]]], {n, 0, 30}]
|
|
CROSSREFS
|
References found in the links are not all included here.
Summing over indices with binary length n gives A335456(n).
The version for Heinz numbers of partitions is A335549.
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.
Cf. A034691, A056986, A108917, A124767, A124770, A158005, A269134, A333218, A333222, A333224, A334030.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|