login
A335518
Number of matching pairs of patterns, the first of length n and the second of length k.
1
1, 1, 1, 3, 3, 3, 13, 13, 25, 13, 75, 75, 185, 213, 75, 541, 541, 1471, 2719, 2053, 541, 4683, 4683, 13265, 32973, 40367, 22313, 4683, 47293, 47293, 136711, 408265, 713277, 625295, 271609, 47293
OFFSET
0,4
COMMENTS
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).
EXAMPLE
Triangle begins:
1
1 1
3 3 3
13 13 25 13
75 75 185 213 75
541 541 1471 2719 2053 541
4683 4683 13265 32973 40367 22313 4683
Row n =2 counts the following pairs:
()<=(1,1) (1)<=(1,1) (1,1)<=(1,1)
()<=(1,2) (1)<=(1,2) (1,2)<=(1,2)
()<=(2,1) (1)<=(2,1) (2,1)<=(2,1)
MATHEMATICA
mstype[q_]:=q/.Table[Union[q][[i]]->i, {i, Length[Union[q]]}];
allnorm[n_]:=If[n<=0, {{}}, Function[s, Array[Count[s, y_/; y<=#]+1&, n]]/@Subsets[Range[n-1]+1]];
Table[Sum[Length[Union[mstype/@Subsets[y, {k}]]], {y, Join@@Permutations/@allnorm[n]}], {n, 0, 5}, {k, 0, n}]
CROSSREFS
Columns k = 0 and k = 1 are both A000670.
Row sums are A335517.
Patterns are ranked by A333217.
Patterns matched by a standard composition are counted by A335454.
Patterns contiguously matched by compositions are counted by A335457.
Minimal patterns avoided by a standard composition are counted by A335465.
Patterns matched by prime indices are counted by A335549.
Sequence in context: A291407 A147823 A341211 * A269347 A183554 A229847
KEYWORD
nonn,tabl,more
AUTHOR
Gus Wiseman, Jun 23 2020
STATUS
approved