cp's OEIS Frontend

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

%I A335515 #12 Jan 28 2024 20:56:42
%S A335515 0,0,0,1,19,257,3167,38909,498235,6811453,100623211,1612937661,
%T A335515 28033056683,526501880989,10639153638795,230269650097469,
%U A335515 5315570416909995,130370239796988957,3385531348514480651,92801566389186549245,2677687663571344712043,81124824154544921317597
%N A335515 Number of patterns of length n matching the pattern (1,2,3).
%C A335515 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 A335515 Andrew Howroyd, <a href="/A335515/b335515.txt">Table of n, a(n) for n = 0..200</a>
%H A335515 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A335515 Gus Wiseman, <a href="https://oeis.org/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%F A335515 a(n) = A000670(n) - A226316(n). - _Andrew Howroyd_, Jan 28 2024
%e A335515 The a(3) = 1 through a(4) = 19 patterns:
%e A335515   (1,2,3)  (1,1,2,3)
%e A335515            (1,2,1,3)
%e A335515            (1,2,2,3)
%e A335515            (1,2,3,1)
%e A335515            (1,2,3,2)
%e A335515            (1,2,3,3)
%e A335515            (1,2,3,4)
%e A335515            (1,2,4,3)
%e A335515            (1,3,2,3)
%e A335515            (1,3,2,4)
%e A335515            (1,3,4,2)
%e A335515            (1,4,2,3)
%e A335515            (2,1,2,3)
%e A335515            (2,1,3,4)
%e A335515            (2,3,1,4)
%e A335515            (2,3,4,1)
%e A335515            (3,1,2,3)
%e A335515            (3,1,2,4)
%e A335515            (4,1,2,3)
%t A335515 allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t A335515 Table[Length[Select[Join@@Permutations/@allnorm[n],MatchQ[#,{___,x_,___,y_,___,z_,___}/;x<y<z]&]],{n,0,6}]
%o A335515 (PARI) seq(n)=Vec( serlaplace(1/(2-exp(x + O(x*x^n)))) - 1/2 - 1/(1+sqrt(1-8*x+8*x^2 + O(x*x^n))), -(n+1)) \\ _Andrew Howroyd_, Jan 28 2024
%Y A335515 The complement A226316 is the avoiding version.
%Y A335515 Compositions matching this pattern are counted by A335514 and ranked by A335479.
%Y A335515 Permutations of prime indices matching this pattern are counted by A335520.
%Y A335515 Patterns are counted by A000670 and ranked by A333217.
%Y A335515 Patterns matching the pattern (1,1) are counted by A019472.
%Y A335515 Permutations matching (1,2,3) are counted by A056986.
%Y A335515 Combinatory separations are counted by A269134.
%Y A335515 Patterns matched by standard compositions are counted by A335454.
%Y A335515 Minimal patterns avoided by a standard composition are counted by A335465.
%Y A335515 Cf. A034691, A158005, A158009, A238279, A333218, A333379, A333942.
%K A335515 nonn
%O A335515 0,5
%A A335515 _Gus Wiseman_, Jun 19 2020
%E A335515 a(9) onwards from _Andrew Howroyd_, Jan 28 2024