A034691 -id:A034691 - cp's OEIS frontend

A317546 Number of multimin partitions of integer partitions of n.

1, 3, 7, 18, 42, 104, 246, 594, 1416, 3391, 8084, 19312, 46041, 109829, 261827, 624254, 1487981, 3546883, 8453770, 20149014, 48021864, 114451536, 272769936, 650084053, 1549312743

Offset: 1

Gus Wiseman, Jul 31 2018

nonn

A multimin partition of m is an ordered multiset partition of m such that the minima of the blocks are weakly increasing.

			The a(3) = 7 multimin partitions of integer partitions of 3:
  (3),
  (1)(2), (12),
  (1)(1)(1), (1)(11), (11)(1), (111).
The a(4) = 18 multimin partitions of integer partitions of 4:
  (4),
  (1)(3), (13),
  (2)(2), (22),
  (1)(1)(2), (1)(12), (11)(2), (12)(1), (112),
  (1)(1)(1)(1), (1)(1)(11), (1)(11)(1), (1)(111), (11)(1)(1), (11)(11), (111)(1), (1111).

Cf. A007716, A020639, A034691, A255397, A300335, A317545.

mmcount[m_List]:=mmcount[m]=If[Length[m]===0,0,1+Plus@@mmcount/@Union[Subsets[Rest[m]]]];
Table[Sum[mmcount[Reverse[ptn]],{ptn,IntegerPartitions[n]}],{n,25}]

a(n) = Sum_{k > 0 : A056239(k) = n} A317545(k).

A335479 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (1,2,3).

Original entry on oeis.org

52, 104, 105, 108, 116, 180, 200, 208, 209, 210, 211, 212, 216, 217, 220, 232, 233, 236, 244, 308, 328, 360, 361, 364, 372, 400, 401, 404, 408, 416, 417, 418, 419, 420, 421, 422, 423, 424, 425, 428, 432, 433, 434, 435, 436, 440, 441, 444, 456, 464, 465, 466

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

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).

			The sequence of terms together with the corresponding compositions begins:
   52: (1,2,3)
  104: (1,2,4)
  105: (1,2,3,1)
  108: (1,2,1,3)
  116: (1,1,2,3)
  180: (2,1,2,3)
  200: (1,3,4)
  208: (1,2,5)
  209: (1,2,4,1)
  210: (1,2,3,2)
  211: (1,2,3,1,1)
  212: (1,2,2,3)
  216: (1,2,1,4)
  217: (1,2,1,3,1)
  220: (1,2,1,1,3)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;x

A382214 Number of normal multisets of size n that can be partitioned into a set of sets.

Original entry on oeis.org

1, 1, 1, 3, 5, 11, 23, 48, 101, 210, 436, 894

Offset: 0

Gus Wiseman, Mar 29 2025

First differs from A382216 at a(9) = 210, A382216(9) = 208.

We call a multiset or multiset partition normal iff it covers an initial interval of positive integers. The size of a multiset is the number of elements, counting multiplicity.

			The normal multiset {1,1,1,1,2,2,3,3,3} has partition {{1},{3},{1,2},{1,3},{1,2,3}}, so is counted under a(9).
The a(1) = 1 through a(5) = 11 multisets:
  {1}  {1,2}  {1,1,2}  {1,1,2,2}  {1,1,1,2,3}
              {1,2,2}  {1,1,2,3}  {1,1,2,2,3}
              {1,2,3}  {1,2,2,3}  {1,1,2,3,3}
                       {1,2,3,3}  {1,1,2,3,4}
                       {1,2,3,4}  {1,2,2,2,3}
                                  {1,2,2,3,3}
                                  {1,2,2,3,4}
                                  {1,2,3,3,3}
                                  {1,2,3,3,4}
                                  {1,2,3,4,4}
                                  {1,2,3,4,5}

Factorizations of this type are counted by A050326, distinct sums A381633.
Normal multiset partitions of this type are counted by A116539, distinct sums A381718.
The complement is counted by A292432.
Twice-partitions of this type are counted by A358914, distinct sums A279785.
The strong version is A381996, complement A292444.
For integer partitions we have A382077, ranks A382200, complement A382078, ranks A293243.
For distinct sums we have A382216, complement A382202.
The case of a unique choice is counted by A382458, distinct sums A382459.
A000670 counts patterns, ranked by A055932 and A333217, necklace A019536.
A001055 count factorizations, strict A045778.
Normal multiset partitions: A034691, A035310, A255906.
Set systems: A050342, A296120, A318361.
Set multipartitions: A089259, A270995, A296119, A318360.
Cf. A000110, A007716, A050320, A116540, A255903, A317532, A326517, A326519, A381990, A381992, A382428, A382460.

allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]] /@ Subsets[Range[n-1]+1]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[mset_]:=Union[Sort[Sort/@(#/.x_Integer:>mset[[x]])]& /@ sps[Range[Length[mset]]]];
Table[Length[Select[allnorm[n],Select[mps[#], UnsameQ@@#&&And@@UnsameQ@@@#&]!={}&]],{n,0,5}]

A104460 Number of hierarchical orderings for n unlabeled elements with 2 possible classes for levels l>=2.

Original entry on oeis.org

1, 4, 13, 46, 154, 533, 1802, 6137, 20729, 69971, 235193, 789000, 2639004, 8807811, 29327841, 97456878, 323206002, 1069923013, 3535612108, 11664423298, 38422208659, 126374059558, 415069188175, 1361443135562, 4459861400156, 14591869576268, 47686017637926

Offset: 1

Thomas Wieder, Mar 09 2005

nonn

Consider a hierarchical ordering of n unlabeled elements into groups as defined in A034691. In addition assume that each level l with l >= 2 can fall into one of two classes A and B. Let | denote a separator among different groups and let : denote a separator between levels. Furthermore, let * denote an unlabeled element which is written as "a" if it falls into class A and as "b" if it falls into class B. As an example with n=4 one can have *|*:ab. In this example one has two groups, where the second group has tree elements, one on level l=1 and two on level l=2. One of the two elements on l=2 belongs to class A, the other to class B.

			For n=3 there are 13 orderings:
*|*|*; *|**; *|*:a; *|*:b; ***; **|a; *:aa; *:a:a; **|b; *:bb; *:b:b; *:a:b; *:b:a.

Alois P. Heinz, Table of n, a(n) for n = 1..600
N. J. A. Sloane and Thomas Wieder, The Number of Hierarchical Orderings, Order 21 (2004), 83-89.

Cf. A034691.

etr:= proc(p) local b; b:=proc(n) option remember; `if`(n=0,1, add(add(d*p(d), d=numtheory[divisors](j)) *b(n-j), j=1..n)/n) end end: a:= etr(n-> 3^(n-1)): seq(a(n), n=1..30); # Alois P. Heinz, Sep 08 2008

etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[ Sum[d*p[d], {d, Divisors[j]}]*b[n-j], {j, 1, n}]/n]; b]; a = etr[Function[3^(#-1)]]; Table[a[n], {n, 1, 30}] (* Jean-François Alcover, Mar 05 2015, after Alois P. Heinz *)
nmax = 30; Rest[CoefficientList[Series[Product[1/(1 - x^k)^(3^(k-1)), {k, 1, nmax}], {x, 0, nmax}], x]] (* Vaclav Kotesovec, Apr 12 2021 *)

G.f.: 1 + Sum_{n>=1} a(n) * x^n = 1 / Product_{n>=1} (1-x^n)^(3^(n-1)).
A104460 is the Euler transform of powers of 3 [1, 3, 9, 27, 81, ...].
a(n) ~ exp(2*sqrt(n/3) - 1/6 + c/3) * 3^(n - 1/4) / (2*sqrt(Pi)*n^(3/4)), where c = Sum_{j>=2} 1/(j * (3^(j-1) - 1)). - Vaclav Kotesovec, Apr 12 2021

A317545 Number of multimin factorizations of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 2, 2, 1, 5, 1, 2, 2, 8, 1, 4, 1, 5, 2, 2, 1, 12, 2, 2, 4, 5, 1, 5, 1, 16, 2, 2, 2, 11, 1, 2, 2, 12, 1, 5, 1, 5, 5, 2, 1, 28, 2, 4, 2, 5, 1, 8, 2, 12, 2, 2, 1, 15, 1, 2, 5, 32, 2, 5, 1, 5, 2, 5, 1, 29, 1, 2, 4, 5, 2, 5, 1, 28, 8, 2, 1, 15, 2, 2, 2, 12, 1, 12, 2, 5, 2, 2, 2, 64, 1, 4, 5, 11, 1, 5, 1, 12, 5

Offset: 1

Gus Wiseman, Jul 31 2018

nonn

A multimin factorizations of n is an ordered factorization of n into factors greater than 1 such that the sequence of minimal primes dividing each factor is weakly increasing.

			The a(36) = 11 multimin factorizations:
  (36),
  (2*18), (4*9), (6*6), (12*3), (18*2),
  (2*2*9), (2*6*3), (4*3*3), (6*2*3),
  (2*2*3*3).

Antti Karttunen, Table of n, a(n) for n = 1..65537

Cf. A007716, A020639, A034691, A255397, A296560, A300335, A317546.

a[n_]:=If[n==1,1,Sum[a[d],{d,Divisors[n/FactorInteger[n][[1,1]]]}]];
Array[a,100]

A317545(n) = if(1==n,1,my(spf = factor(n)[1,1]); sumdiv(n/spf,d,A317545(d))); \\ Antti Karttunen, Sep 10 2018

memo317545 = Map(); \\ Memoized version.
A317545(n) = if(1==n,1,if(mapisdefined(memo317545, n), mapget(memo317545, n), my(spf = factor(n)[1,1], v = sumdiv(n/spf,d,A317545(d))); mapput(memo317545, n, v); (v))); \\ Antti Karttunen, Sep 10 2018

a(1) = 1; a(n > 1) = Sum_{d|(n/p)} a(d), where p is the smallest prime dividing n.

More terms from Antti Karttunen, Sep 10 2018

A333765 Number of co-Lyndon factorizations of the k-th composition in standard order.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 2, 2, 4, 5, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 4, 2, 4, 4, 7, 7, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 1, 2, 2, 2, 1, 2, 2, 2, 2, 5, 2, 5, 2, 4, 4, 9, 4, 7, 7, 12, 11, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 4, 1

Offset: 0

Gus Wiseman, Apr 13 2020

nonn

We define the co-Lyndon product of two or more finite sequences to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (2,3,1) with (2,1,3) is (2,1,2,3,1,3), the product of (2,2,1) with (2,1,3) is (2,1,2,2,1,3), and the product of (1,2,2) with (2,1,2,1) is (1,2,1,2,1,2,2). A co-Lyndon factorization of a composition c is a multiset of compositions whose co-Lyndon product is c.
A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.
Also the number of multiset partitions of the co-Lyndon-word factorization of the n-th composition in standard order.

			The a(54) = 5, a(61) = 7, and a(237) = 9 factorizations:
  ((1,2,1,2))      ((1,1,1,2,1))        ((1,1,2,1,2,1))
  ((1),(2,1,2))    ((1),(1,1,2,1))      ((1),(1,2,1,2,1))
  ((1,2),(2,1))    ((1,1),(1,2,1))      ((1,1),(2,1,2,1))
  ((2),(1,2,1))    ((2,1),(1,1,1))      ((1,2,1),(1,2,1))
  ((1),(2),(2,1))  ((1),(1),(1,2,1))    ((2,1),(1,1,2,1))
                   ((1),(1,1),(2,1))    ((1),(1),(2,1,2,1))
                   ((1),(1),(1),(2,1))  ((1,1),(2,1),(2,1))
                                        ((1),(2,1),(1,2,1))
                                        ((1),(1),(2,1),(2,1))

The dual version is A333940.
Binary necklaces are counted by A000031.
Necklace compositions are counted by A008965.
Necklaces covering an initial interval are counted by A019536.
Lyndon compositions are counted by A059966.
Numbers whose reversed binary expansion is a necklace are A328595.
Numbers whose prime signature is a necklace are A329138.
Length of Lyndon factorization of binary expansion is A211100.
Length of co-Lyndon factorization of binary expansion is A329312.
Length of co-Lyndon factorization of reversed binary expansion is A329326.
Length of Lyndon factorization of reversed binary expansion is A329313.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Reversed co-necklaces are A328595.
- Length of Lyndon factorization is A329312.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Dealings are counted by A333939.
- Reversed necklaces are A333943.
- Length of co-Lyndon factorization is A334029.
- Combinatory separations are A334030.
Cf. A000740, A001037, A034691, A060223, A211100, A269134, A292884, A328596.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
colynprod[]:={};colynprod[{},b_List]:=b;colynprod[a_List,{}]:=a;colynprod[a_List]:=a;
colynprod[{x_,a___},{y_,b___}]:=Switch[Ordering[If[x=!=y,{x,y},{colynprod[{a},{x,b}],colynprod[{x,a},{b}]}]],{1,2},Prepend[colynprod[{a},{y,b}],x],{2,1},Prepend[colynprod[{x,a},{b}],y]];
colynprod[a_List,b_List,c__List]:=colynprod[a,colynprod[b,c]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
dealings[q_]:=Union[Function[ptn,Sort[q[[#]]&/@ptn]]/@sps[Range[Length[q]]]];
Table[Length[Select[dealings[stc[n]],colynprod@@#==stc[n]&]],{n,0,100}]

For n > 0, Sum_{k = 2^(n-1)..2^n-1} a(k) = A034691(n).

A335470 Number of compositions of n matching the pattern (1,2,1).

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 9, 24, 61, 141, 322, 713, 1543, 3289, 6907, 14353, 29604, 60640, 123522, 250645, 506808, 1022197, 2057594, 4135358, 8301139, 16648165, 33364948, 66831721, 133814251, 267850803, 536026676, 1072528081, 2145745276, 4292485526, 8586405894, 17174865820

Offset: 0

Gus Wiseman, Jun 17 2020

nonn

Also the number of (1,1,2)-matching or (2,1,1)-matching compositions.
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).
A composition of n is a finite sequence of positive integers summing to n.

			The a(4) = 1 through a(6) = 9 compositions:
  (121)  (131)   (141)
         (1121)  (1131)
         (1211)  (1212)
                 (1221)
                 (1311)
                 (2121)
                 (11121)
                 (11211)
                 (12111)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for prime indices is A335446.
These compositions are ranked by A335466.
The complement A335471 is the avoiding version.
The (2,1,2)-matching version is A335472.
The version for patterns is A335509.
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Compositions are counted by A011782.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a standard composition are counted by A335465.
Compositions matching (1,2,3) are counted by A335514.
Cf. A261982, A034691, A056986, A106356, A238279, A333755, A335454.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,_,y_,_,x_,_}/;x

a(n > 0) = 2^(n - 1) - A335471(n).

Terms a(21) and beyond from Andrew Howroyd, Dec 31 2020

A335471 Number of compositions of n avoiding the pattern (1,2,1).

Original entry on oeis.org

1, 1, 2, 4, 7, 13, 23, 40, 67, 115, 190, 311, 505, 807, 1285, 2031, 3164, 4896, 7550, 11499, 17480, 26379, 39558, 58946, 87469, 129051, 189484, 277143, 403477, 584653, 844236, 1213743, 1738372, 2481770, 3528698, 5003364, 7070225, 9958387, 13982822, 19580613, 27333403

Offset: 0

Gus Wiseman, Jun 17 2020

nonn

Also the number of (1,1,2)-avoiding or (2,1,1)-avoiding compositions.
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).
A composition of n is a finite sequence of positive integers summing to n.

			The a(0) = 1 through a(5) = 13 compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (13)    (14)
                 (21)   (22)    (23)
                 (111)  (31)    (32)
                        (112)   (41)
                        (211)   (113)
                        (1111)  (122)
                                (212)
                                (221)
                                (311)
                                (1112)
                                (2111)
                                (11111)

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for patterns is A001710.
The version for prime indices is A335449.
These compositions are ranked by A335467.
The complement A335470 is the matching version.
The (2,1,2)-avoiding version is A335473.
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Compositions are counted by A011782.
Compositions avoiding (1,2,3) are counted by A102726.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A034691, A056986, A106356, A232464, A238279, A333213, A333755.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,_,y_,_,x_,_}/;x

a(n)={local(Cache=Map()); my(F(n,m,k)=if(m>n, m=n); if(m==0, n==0, my(hk=[n,m,k], z); if(!mapisdefined(Cache,hk,&z), z=self()(n,m-1,k) + k*sum(i=1,n\m, self()(n-i*m, m-1, k+i)); mapput(Cache, hk, z)); z)); F(n,n,1)} \\ Andrew Howroyd, Dec 31 2020

a(n > 0) = 2^(n - 1) - A335470(n).

a(n) = F(n,n,1) where F(n,m,k) = F(n,m-1,k) + k*(Sum_{i=1..floor(n/m)} F(n-i*m, m-1, k+i)) for m > 0 with F(0,m,k)=1 and F(n,0,k)=0 otherwise. - Andrew Howroyd, Dec 31 2020

Terms a(21) and beyond from Andrew Howroyd, Dec 31 2020

A335473 Number of compositions of n avoiding the pattern (2,1,2).

Original entry on oeis.org

1, 1, 2, 4, 8, 15, 29, 55, 103, 190, 347, 630, 1134, 2028, 3585, 6291, 10950, 18944, 32574, 55692, 94618, 159758, 268147, 447502, 743097, 1227910, 2020110, 3308302, 5394617, 8757108, 14155386, 22784542, 36529813, 58343498, 92850871, 147254007, 232750871, 366671436

Offset: 0

Gus Wiseman, Jun 17 2020

nonn

Also the number of (1,2,2) or (2,2,1)-avoiding compositions.
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).
A composition of n is a finite sequence of positive integers summing to n.

			The a(0) = 1 through a(5) = 15 compositions:
  ()  (1)  (2)   (3)    (4)     (5)
           (11)  (12)   (13)    (14)
                 (21)   (22)    (23)
                 (111)  (31)    (32)
                        (112)   (41)
                        (121)   (113)
                        (211)   (122)
                        (1111)  (131)
                                (221)
                                (311)
                                (1112)
                                (1121)
                                (1211)
                                (2111)
                                (11111)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for patterns is A001710.
The version for prime indices is A335450.
These compositions are ranked by A335469.
The (1,2,1)-avoiding version is A335471.
The complement A335472 is the matching version.
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Compositions are counted by A011782.
Compositions avoiding (1,2,3) are counted by A102726.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A261982, A034691, A056986, A106356, A232464, A238279, A333755.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MatchQ[#,{_,x_,_,y_,_,x_,_}/;x>y]&]],{n,0,10}]

a(n)={local(Cache=Map()); my(F(n,m,k) = if(m>n, n==0, my(hk=[n,m,k], z); if(!mapisdefined(Cache,hk,&z), z=self()(n,m+1,k) + k*sum(i=1,n\m, self()(n-i*m, m+1, k+i)); mapput(Cache, hk, z)); z)); F(n,1,1)} \\ Andrew Howroyd, Dec 31 2020

a(n > 0) = 2^(n - 1) - A335472(n).

a(n) = F(n,1,1) where F(n,m,k) = F(n,m+1,k) + k*(Sum_{i=1..floor(n/m)} F(n-i*m, m+1, k+i)) for m <= n with F(0,m,k)=1 and F(n,m,k)=0 otherwise. - Andrew Howroyd, Dec 31 2020

Terms a(21) and beyond from Andrew Howroyd, Dec 31 2020

A335480 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (1,3,2).

Original entry on oeis.org

50, 98, 101, 102, 114, 178, 194, 196, 197, 198, 202, 203, 205, 206, 210, 226, 229, 230, 242, 306, 324, 354, 357, 358, 370, 386, 388, 389, 390, 393, 394, 395, 396, 397, 398, 402, 404, 405, 406, 407, 410, 411, 413, 414, 418, 421, 422, 434, 450, 452, 453, 454

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

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).

			The sequence of terms together with the corresponding compositions begins:
   50: (1,3,2)
   98: (1,4,2)
  101: (1,3,2,1)
  102: (1,3,1,2)
  114: (1,1,3,2)
  178: (2,1,3,2)
  194: (1,5,2)
  196: (1,4,3)
  197: (1,4,2,1)
  198: (1,4,1,2)
  202: (1,3,2,2)
  203: (1,3,2,1,1)
  205: (1,3,1,2,1)
  206: (1,3,1,1,2)
  210: (1,2,3,2)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Permutations matching (1,3,2,4) are counted by A158009.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;x

cp's OEIS Frontend

A317546 Number of multimin partitions of integer partitions of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A335479 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (1,2,3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A382214 Number of normal multisets of size n that can be partitioned into a set of sets.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A104460 Number of hierarchical orderings for n unlabeled elements with 2 possible classes for levels l>=2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A317545 Number of multimin factorizations of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A333765 Number of co-Lyndon factorizations of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A335470 Number of compositions of n matching the pattern (1,2,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A335471 Number of compositions of n avoiding the pattern (1,2,1).

Views