|
%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
|
