A335508 - OEIS

%I #21 Jan 28 2024 18:11:04

%S 0,0,0,1,9,91,993,12013,160275,2347141,37496163,649660573,12142311195,

%T 243626199181,5224710549243,119294328993853,2889836999693355,

%U 74037381200415901,2000383612949821323,56850708386783835133,1695491518035158123115,52949018580275965241821

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

%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 Alois P. Heinz, <a href="/A335508/b335508.txt">Table of n, a(n) for n = 0..424</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 a(n) = Sum_{k=3..n} A276922(n,k). - _Alois P. Heinz_, Jan 28 2024

%F a(n) = A000670(n) - A080599(n). - _Andrew Howroyd_, Jan 28 2024

%e The a(3) = 1 through a(4) = 9 patterns:

%e   (1,1,1)  (1,1,1,1)

%e            (1,1,1,2)

%e            (1,1,2,1)

%e            (1,2,1,1)

%e            (1,2,2,2)

%e            (2,1,1,1)

%e            (2,1,2,2)

%e            (2,2,1,2)

%e            (2,2,2,1)

%p b:= proc(n, k) option remember; `if`(n=0, 1, add(

%p       b(n-i, k)*binomial(n, i), i=1..min(n, k)))

%p     end:

%p a:= n-> b(n$2)-b(n, 2):

%p seq(a(n), n=0..21);  # _Alois P. Heinz_, Jan 28 2024

%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_,___,x_,___}]&]],{n,0,6}]

%Y The complement A080599 is the avoiding version.

%Y Permutations of prime indices matching this pattern are counted by A335510.

%Y Compositions matching this pattern are counted by A335455 and ranked by A335512.

%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, A232464, A238279, A292884, A333175, A333755, A335451, A335456, A335457, A335458.

%Y Cf. A276922.

%K nonn

%O 0,5

%A _Gus Wiseman_, Jun 18 2020

%E a(9)-a(21) from _Alois P. Heinz_, Jan 28 2024