cp's OEIS Frontend

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

%I A335517 #6 Jun 24 2020 07:21:56
%S A335517 1,2,9,64,623,7866,122967
%N A335517 Number of matching pairs of patterns, the longest having length n.
%C A335517 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 A335517 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A335517 Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%e A335517 The a(0) = 1 through a(2) = 9 pairs of patterns:
%e A335517   ()<=()    ()<=(1)      ()<=(1,1)
%e A335517            (1)<=(1)      ()<=(1,2)
%e A335517                          ()<=(2,1)
%e A335517                         (1)<=(1,1)
%e A335517                         (1)<=(1,2)
%e A335517                         (1)<=(2,1)
%e A335517                       (1,1)<=(1,1)
%e A335517                       (1,2)<=(1,2)
%e A335517                       (2,1)<=(2,1)
%t A335517 mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
%t A335517 allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t A335517 Table[Sum[Length[Union[mstype/@Subsets[y]]],{y,Join@@Permutations/@allnorm[n]}],{n,0,5}]
%Y A335517 Row sums of A335518.
%Y A335517 Patterns are counted by A000670 and ranked by A333217.
%Y A335517 Patterns matched by a standard composition are counted by A335454.
%Y A335517 Patterns contiguously matched by compositions are counted by A335457.
%Y A335517 Minimal patterns avoided by a standard composition are counted by A335465.
%Y A335517 Patterns matched by prime indices are counted by A335549.
%Y A335517 Cf. A011782, A034691, A056986, A124771, A269134, A329744, A333257, A334299.
%K A335517 nonn,more
%O A335517 0,2
%A A335517 _Gus Wiseman_, Jun 23 2020