cp's OEIS Frontend

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

%I A335508 #21 Jan 28 2024 18:11:04
%S A335508 0,0,0,1,9,91,993,12013,160275,2347141,37496163,649660573,12142311195,
%T A335508 243626199181,5224710549243,119294328993853,2889836999693355,
%U A335508 74037381200415901,2000383612949821323,56850708386783835133,1695491518035158123115,52949018580275965241821
%N A335508 Number of patterns of length n matching the pattern (1,1,1).
%C A335508 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 A335508 Alois P. Heinz, <a href="/A335508/b335508.txt">Table of n, a(n) for n = 0..424</a>
%H A335508 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A335508 Gus Wiseman, <a href="https://oeis.org/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%F A335508 a(n) = Sum_{k=3..n} A276922(n,k). - _Alois P. Heinz_, Jan 28 2024
%F A335508 a(n) = A000670(n) - A080599(n). - _Andrew Howroyd_, Jan 28 2024
%e A335508 The a(3) = 1 through a(4) = 9 patterns:
%e A335508   (1,1,1)  (1,1,1,1)
%e A335508            (1,1,1,2)
%e A335508            (1,1,2,1)
%e A335508            (1,2,1,1)
%e A335508            (1,2,2,2)
%e A335508            (2,1,1,1)
%e A335508            (2,1,2,2)
%e A335508            (2,2,1,2)
%e A335508            (2,2,2,1)
%p A335508 b:= proc(n, k) option remember; `if`(n=0, 1, add(
%p A335508       b(n-i, k)*binomial(n, i), i=1..min(n, k)))
%p A335508     end:
%p A335508 a:= n-> b(n$2)-b(n, 2):
%p A335508 seq(a(n), n=0..21);  # _Alois P. Heinz_, Jan 28 2024
%t A335508 allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
%t A335508 Table[Length[Select[Join@@Permutations/@allnorm[n],MatchQ[#,{___,x_,___,x_,___,x_,___}]&]],{n,0,6}]
%Y A335508 The complement A080599 is the avoiding version.
%Y A335508 Permutations of prime indices matching this pattern are counted by A335510.
%Y A335508 Compositions matching this pattern are counted by A335455 and ranked by A335512.
%Y A335508 Patterns are counted by A000670 and ranked by A333217.
%Y A335508 Patterns matching the pattern (1,1) are counted by A019472.
%Y A335508 Combinatory separations are counted by A269134.
%Y A335508 Patterns matched by standard compositions are counted by A335454.
%Y A335508 Minimal patterns avoided by a standard composition are counted by A335465.
%Y A335508 Patterns matching (1,2,3) are counted by A335515.
%Y A335508 Cf. A034691, A056986, A232464, A238279, A292884, A333175, A333755, A335451, A335456, A335457, A335458.
%Y A335508 Cf. A276922.
%K A335508 nonn
%O A335508 0,5
%A A335508 _Gus Wiseman_, Jun 18 2020
%E A335508 a(9)-a(21) from _Alois P. Heinz_, Jan 28 2024