|
%I #11 Dec 31 2020 15:36:43
%S 0,0,0,1,15,181,2163,27133,364395,5272861,82289163,1383131773,
%T 24978057195,483269202781,9987505786443,219821796033853,
%U 5137810967933355,127169580176271901,3324712113052429323,91585136315240091133,2652142325158529483115,80562824634615270041821
%N Number of patterns of length n matching the pattern (1,1,2).
%C Also the number of (1,2,1)-matching patterns of length n.
%C Also the number of (2,1,2)-matching patterns of 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 Andrew Howroyd, <a href="/A335509/b335509.txt">Table of n, a(n) for n = 0..200</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H Gus Wiseman, <a href="https://oeis.org/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%F E.g.f.: 1/(2-exp(x)) - (2-2*x+x^2)/(2*(1-x)^2). - _Andrew Howroyd_, Dec 31 2020
%e The a(3) = 1 through a(4) = 15 patterns:
%e (1,1,2) (1,1,1,2)
%e (1,1,2,1)
%e (1,1,2,2)
%e (1,1,2,3)
%e (1,1,3,2)
%e (1,2,1,2)
%e (1,2,1,3)
%e (1,2,2,3)
%e (1,3,1,2)
%e (2,1,1,2)
%e (2,1,1,3)
%e (2,1,2,3)
%e (2,2,1,3)
%e (2,2,3,1)
%e (3,1,1,2)
%t allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t Table[Length[Select[Join@@Permutations/@allnorm[n],MatchQ[#,{___,x_,___,x_,___,y_,___}/;x<y]&]],{n,0,6}]
%o (PARI) seq(n)={Vec(serlaplace(1/(2-exp(x + O(x*x^n))) - (2-2*x+x^2)/(2*(1-x)^2)), -(n+1))} \\ _Andrew Howroyd_, Dec 31 2020
%Y The complement A001710 is the avoiding version.
%Y Compositions matching this pattern are counted by A335470 and ranked by A335476.
%Y Permutations of prime indices matching this pattern are counted by A335446.
%Y Patterns are counted by A000670 and ranked by A333217.
%Y Patterns matching the pattern (1,1) are counted by A019472.
%Y Combinatory separations are counted by A269134.
%Y Patterns matched by standard compositions are counted by A335454.
%Y Minimal patterns avoided by a standard composition are counted by A335465.
%Y Patterns matching (1,2,3) are counted by A335515.
%Y Cf. A034691, A056986, A238279, A292884, A333755, A335456, A335457.
%K nonn
%O 0,5
%A _Gus Wiseman_, Jun 18 2020
%E Terms a(10) and beyond from _Andrew Howroyd_, Dec 31 2020
|
