cp's OEIS Frontend

A335456 Number of normal patterns matched by compositions of n.

%I A335456 #17 Mar 14 2025 12:35:25
%S A335456 1,2,5,12,32,84,211,556,1446,3750,9824,25837,67681,178160,468941,
%T A335456 1233837,3248788,8554709
%N A335456 Number of normal patterns matched by compositions of n.
%C A335456 A composition of n is a finite sequence of positive integers summing to n.
%C A335456 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 A335456 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A335456 Gus Wiseman, <a href="https://oeis.org/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%e A335456 The 8 compositions of 4 together with the a(4) = 32 patterns they match:
%e A335456   4:   31:   13:   22:   211:   121:   112:   1111:
%e A335456 -----------------------------------------------------
%e A335456   ()   ()    ()    ()    ()     ()     ()     ()
%e A335456   (1)  (1)   (1)   (1)   (1)    (1)    (1)    (1)
%e A335456        (21)  (12)  (11)  (11)   (11)   (11)   (11)
%e A335456                          (21)   (12)   (12)   (111)
%e A335456                          (211)  (21)   (112)  (1111)
%e A335456                                 (121)
%t A335456 mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
%t A335456 Table[Sum[Length[Union[mstype/@Subsets[y]]],{y,Join@@Permutations/@IntegerPartitions[n]}],{n,0,8}]
%Y A335456 References found in the link are not all included here.
%Y A335456 The version for standard compositions is A335454.
%Y A335456 The contiguous case is A335457.
%Y A335456 The version for Heinz numbers of partitions is A335549.
%Y A335456 Patterns are counted by A000670 and ranked by A333217.
%Y A335456 The n-th composition has A124771(n) distinct consecutive subsequences.
%Y A335456 Knapsack compositions are counted by A325676 and ranked by A333223.
%Y A335456 The n-th composition has A333257(n) distinct subsequence-sums.
%Y A335456 The n-th composition has A334299(n) distinct subsequences.
%Y A335456 Minimal patterns avoided by a standard composition are counted by A335465.
%Y A335456 Cf. A034691, A056986, A106356, A108917, A124770, A269134, A329744, A333224, A335458.
%K A335456 nonn,more
%O A335456 0,2
%A A335456 _Gus Wiseman_, Jun 16 2020
%E A335456 a(14)-a(16) from _Jinyuan Wang_, Jun 26 2020
%E A335456 a(17) from _John Tyler Rascoe_, Mar 14 2025