cp's OEIS Frontend

A335509 Number of patterns of length n matching the pattern (1,1,2).

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