cp's OEIS Frontend

A335837 Number of normal patterns matched by integer partitions of n.

%I A335837 #17 May 09 2025 07:12:39
%S A335837 1,2,5,9,18,31,54,89,146,228,358,545,821,1219,1795,2596,3741,5323,
%T A335837 7521,10534,14659,20232,27788,37897,51410,69347,93111,124348,165378,
%U A335837 218924,288646,379021,495864,646272,839490,1086693,1402268,1803786,2313498,2958530,3773093
%N A335837 Number of normal patterns matched by integer partitions of n.
%C A335837 We define a (normal) 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 A335837 Christian Sievers, <a href="/A335837/b335837.txt">Table of n, a(n) for n = 0..2000</a>
%H A335837 Wikipedia, <a href="https://en.wikipedia.org/wiki/Permutation_pattern">Permutation pattern</a>
%H A335837 Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid.</a>
%e A335837 The a(0) = 1 through a(4) = 18  pairs of a partition with a matched pattern:
%e A335837   ()/()  (1)/()   (2)/()     (3)/()       (4)/()
%e A335837          (1)/(1)  (2)/(1)    (3)/(1)      (4)/(1)
%e A335837                   (11)/()    (21)/()      (31)/()
%e A335837                   (11)/(1)   (21)/(1)     (31)/(1)
%e A335837                   (11)/(11)  (21)/(21)    (31)/(21)
%e A335837                              (111)/()     (22)/()
%e A335837                              (111)/(1)    (22)/(1)
%e A335837                              (111)/(11)   (22)/(11)
%e A335837                              (111)/(111)  (211)/()
%e A335837                                           (211)/(1)
%e A335837                                           (211)/(11)
%e A335837                                           (211)/(21)
%e A335837                                           (211)/(211)
%e A335837                                           (1111)/()
%e A335837                                           (1111)/(1)
%e A335837                                           (1111)/(11)
%e A335837                                           (1111)/(111)
%e A335837                                           (1111)/(1111)
%t A335837 mstype[q_]:=q/.Table[Union[q][[i]]->i,{i,Length[Union[q]]}];
%t A335837 Table[Sum[Length[Union[mstype/@Subsets[y]]],{y,IntegerPartitions[n]}],{n,0,8}]
%o A335837 (PARI)
%o A335837 lista(n) = {
%o A335837   my(v=vector(n+1,i,1+x*O(x^n)));
%o A335837   for(k=1,n,
%o A335837     v=vector(n\(k+1)+1,i,
%o A335837         (1-x^(i*k))/(1-x^k)*v[i] + sum(j=i,n\k,x^(j*k)*v[j+1]) +
%o A335837         x^(k*i)/(1-x^k)^2*v[1] ) );
%o A335837   Vec(v[1]) } \\ _Christian Sievers_, May 08 2025
%Y A335837 The version for compositions in standard order is A335454.
%Y A335837 The version for compositions is A335456.
%Y A335837 The version for Heinz numbers of partitions is A335549.
%Y A335837 The contiguous case is A335838.
%Y A335837 Patterns are counted by A000670 and ranked by A333217.
%Y A335837 Patterns contiguously matched by prime indices are A335516.
%Y A335837 Contiguous divisors are counted by A335519.
%Y A335837 Minimal patterns avoided by prime indices are counted by A335550.
%Y A335837 Cf. A000005, A056986, A108917, A269134, A333257, A334299, A335458, A335465.
%K A335837 nonn
%O A335837 0,2
%A A335837 _Gus Wiseman_, Jun 27 2020
%E A335837 a(18) corrected by and a(19)-a(22) from _Jinyuan Wang_, Jun 27 2020
%E A335837 More terms from _Christian Sievers_, May 08 2025