%I #6 Jun 24 2020 07:21:56

%S 1,2,9,64,623,7866,122967

%N Number of matching pairs of patterns, the longest having length n.

%C 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).

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>

%H Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>

%e The a(0) = 1 through a(2) = 9 pairs of patterns:

%e ()<=() ()<=(1) ()<=(1,1)

%e (1)<=(1) ()<=(1,2)

%e ()<=(2,1)

%e (1)<=(1,1)

%e (1)<=(1,2)

%e (1)<=(2,1)

%e (1,1)<=(1,1)

%e (1,2)<=(1,2)

%e (2,1)<=(2,1)

%t mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];

%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];

%t Table[Sum[Length[Union[mstype/@Subsets[y]]],{y,Join@@Permutations/@allnorm[n]}],{n,0,5}]

%Y Row sums of A335518.

%Y Patterns are counted by A000670 and ranked by A333217.

%Y Patterns matched by a standard composition are counted by A335454.

%Y Patterns contiguously matched by compositions are counted by A335457.

%Y Minimal patterns avoided by a standard composition are counted by A335465.

%Y Patterns matched by prime indices are counted by A335549.

%Y Cf. A011782, A034691, A056986, A124771, A269134, A329744, A333257, A334299.

%K nonn,more

%O 0,2

%A _Gus Wiseman_, Jun 23 2020