|
| |
|
|
A335456
|
|
Number of normal patterns matched by compositions of n.
|
|
61
|
|
|
|
1, 2, 5, 12, 32, 84, 211, 556, 1446, 3750, 9824, 25837, 67681, 178160, 468941, 1233837, 3248788
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
A composition of n is a finite sequence of positive integers summing to n.
We define a 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
|
|
|
|
EXAMPLE
|
The 8 compositions of 4 together with the a(4) = 32 patterns they match:
4: 31: 13: 22: 211: 121: 112: 1111:
-----------------------------------------------------
() () () () () () () ()
(1) (1) (1) (1) (1) (1) (1) (1)
(21) (12) (11) (11) (11) (11) (11)
(21) (12) (12) (111)
(211) (21) (112) (1111)
(121)
|
|
|
MATHEMATICA
|
mstype[q_]:=q/.Table[Union[q][[i]]->i, {i, Length[Union[q]]}];
Table[Sum[Length[Union[mstype/@Subsets[y]]], {y, Join@@Permutations/@IntegerPartitions[n]}], {n, 0, 8}]
|
|
|
CROSSREFS
|
References found in the link are not all included here.
The version for standard compositions is A335454.
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 patterns avoided by a standard composition are counted by A335465.
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
