cp's OEIS Frontend

A335518 Number of matching pairs of patterns, the first of length n and the second of length k.

%I A335518 #4 Jun 24 2020 07:22:13
%S A335518 1,1,1,3,3,3,13,13,25,13,75,75,185,213,75,541,541,1471,2719,2053,541,
%T A335518 4683,4683,13265,32973,40367,22313,4683,47293,47293,136711,408265,
%U A335518 713277,625295,271609,47293
%N A335518 Number of matching pairs of patterns, the first of length n and the second of length k.
%C A335518 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 A335518 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A335518 Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%e A335518 Triangle begins:
%e A335518      1
%e A335518      1     1
%e A335518      3     3     3
%e A335518     13    13    25    13
%e A335518     75    75   185   213    75
%e A335518    541   541  1471  2719  2053   541
%e A335518   4683  4683 13265 32973 40367 22313  4683
%e A335518 Row n =2 counts the following pairs:
%e A335518   ()<=(1,1)  (1)<=(1,1)  (1,1)<=(1,1)
%e A335518   ()<=(1,2)  (1)<=(1,2)  (1,2)<=(1,2)
%e A335518   ()<=(2,1)  (1)<=(2,1)  (2,1)<=(2,1)
%t A335518 mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
%t A335518 allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t A335518 Table[Sum[Length[Union[mstype/@Subsets[y,{k}]]],{y,Join@@Permutations/@allnorm[n]}],{n,0,5},{k,0,n}]
%Y A335518 Columns k = 0 and k = 1 are both A000670.
%Y A335518 Row sums are A335517.
%Y A335518 Patterns are ranked by A333217.
%Y A335518 Patterns matched by a standard composition are counted by A335454.
%Y A335518 Patterns contiguously matched by compositions are counted by A335457.
%Y A335518 Minimal patterns avoided by a standard composition are counted by A335465.
%Y A335518 Patterns matched by prime indices are counted by A335549.
%Y A335518 Cf. A011782, A034691, A056986, A124771, A269134, A329744, A333257, A334299.
%K A335518 nonn,tabl,more
%O A335518 0,4
%A A335518 _Gus Wiseman_, Jun 23 2020