A324170 -id:A324170 - cp's OEIS frontend

A324173 Regular triangle read by rows where T(n,k) is the number of set partitions of {1,...,n} with k topologically connected components.

1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 2, 6, 6, 1, 0, 6, 15, 20, 10, 1, 0, 21, 51, 65, 50, 15, 1, 0, 85, 203, 252, 210, 105, 21, 1, 0, 385, 912, 1120, 938, 560, 196, 28, 1, 0, 1907, 4527, 5520, 4620, 2898, 1302, 336, 36, 1, 0, 10205, 24370, 29700, 24780, 15792, 7812, 2730, 540, 45, 1

Offset: 0

Gus Wiseman, Feb 17 2019

A set partition is crossing if it contains a pair of blocks of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

The topologically connected components of a set partition correspond to the blocks of its minimal non-crossing coarsening.

			Triangle begins:
     1
     0     1
     0     1     1
     0     1     3     1
     0     2     6     6     1
     0     6    15    20    10     1
     0    21    51    65    50    15     1
     0    85   203   252   210   105    21     1
     0   385   912  1120   938   560   196    28     1
     0  1907  4527  5520  4620  2898  1302   336    36     1
     0 10205 24370 29700 24780 15792  7812  2730   540    45     1
Row n = 4 counts the following set partitions:
  {{1234}}    {{1}{234}}  {{1}{2}{34}}  {{1}{2}{3}{4}}
  {{13}{24}}  {{12}{34}}  {{1}{23}{4}}
              {{123}{4}}  {{12}{3}{4}}
              {{124}{3}}  {{1}{24}{3}}
              {{134}{2}}  {{13}{2}{4}}
              {{14}{23}}  {{14}{2}{3}}

FindStat, The number of topologically connected components of a set partition.

Row sums are A000110. Column k = 1 is A099947.
Cf. A000108, A001263, A002061, A002662, A007297, A016098, A048993, A054726, A293510, A305078, A305079, A323818.
Cf. A324166, A324167, A324169, A324170, A324171, A324172.

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
crosscmpts[stn_]:=csm[Union[Subsets[stn,{1}],Select[Subsets[stn,{2}],croXQ]]];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
Table[Length[Select[sps[Range[n]],Length[crosscmpts[#]]==k&]],{n,0,8},{k,0,n}]

A326210 Number of labeled simple graphs with vertices {1..n} containing a nesting pair of edges, where two edges {a,b}, {c,d} are nesting if a < c and b > d or a > c and b < d.

Original entry on oeis.org

0, 0, 0, 0, 16, 672, 29888, 2071936, 268204288, 68717285888, 35184350796800, 36028796807919616, 73786976292712960000, 302231454903635611721728, 2475880078570760326175178752, 40564819207303340845566684397568, 1329227995784915872903782635437883392

Offset: 0

Gus Wiseman, Jun 19 2019

nonn

Also simple graphs containing a crossing pair of edges, where two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b.

Also simple graphs such that, if the edges are listed in lexicographic order, their maxima (seconds) are not weakly increasing.

			The a(4) = 16 nesting edge-sets:
  {14,23}
  {12,14,23}
  {13,14,23}
  {14,23,24}
  {14,23,34}
  {12,13,14,23}
  {12,14,23,24}
  {12,14,23,34}
  {13,14,23,24}
  {13,14,23,34}
  {14,23,24,34}
  {12,13,14,23,24}
  {12,13,14,23,34}
  {12,14,23,24,34}
  {13,14,23,24,34}
  {12,13,14,23,24,34}
The a(4) = 16 crossing edge-sets:
  {13,24}
  {12,13,24}
  {13,14,24}
  {13,23,24}
  {13,24,34}
  {12,13,14,24}
  {12,13,23,24}
  {12,13,24,34}
  {13,14,23,24}
  {13,14,24,34}
  {13,23,24,34}
  {12,13,14,23,24}
  {12,13,14,24,34}
  {12,13,23,24,34}
  {13,14,23,24,34}
  {12,13,14,23,24,34}

Andrew Howroyd, Table of n, a(n) for n = 0..50

Non-nesting graphs are A054726.
Nesting digraphs are A326209.
Nesting (or crossing) set partitions are A016098.
MM-numbers of nesting multiset partitions are A326256.
Cf. A001519, A006125, A095661, A324170, A324172, A324326.
Cf. A326211, A326243, A326244, A326248, A326250.

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],!OrderedQ[Last/@#]&]],{n,0,5}]

seq(n)={my(p=1 + 3/2*x - x^2 - x/2*sqrt(1 - 12*x + 4*x^2 + O(x^n))); concat([0], vector(n, k, 2^binomial(k,2)-polcoef(p,k)))} \\ Andrew Howroyd, Aug 26 2019

A006125(n) = a(n) + A054726(n).

Terms a(7) and beyond from Andrew Howroyd, Aug 26 2019

A326243 Number of capturing set partitions of {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 1, 11, 80, 503, 2993, 17609, 105017, 644528, 4107600, 27313805, 189866541, 1379728831, 10470032837, 82833202559, 681977545967, 5832430910181, 51723181525978, 474866750479993, 4506706112772881, 44151975623559477, 445958774322599940, 4638590033810841345

Offset: 0

Gus Wiseman, Jun 19 2019

nonn

A set partition is capturing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

			The a(5) = 11 capturing set partitions:
  {{1,2,5},{3,4}}
  {{1,3,4},{2,5}}
  {{1,3,5},{2,4}}
  {{1,4},{2,3,5}}
  {{1,4,5},{2,3}}
  {{1,5},{2,3,4}}
  {{1},{2,5},{3,4}}
  {{1,4},{2,3},{5}}
  {{1,5},{2},{3,4}}
  {{1,5},{2,3},{4}}
  {{1,5},{2,4},{3}}

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

Non-capturing set partitions are A054391.
Crossing and nesting set partitions are (both) A016098.
Cf. A000108, A000110, A001519, A054391, A058681, A122880, A324170.
Cf. A326209, A326211, A326237, A326246, A326249, A326255, A326259.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;xt||x>z&&y

a(n) = A000110(n) - A054391(n).

a(12) and beyond from Christian Sievers, Aug 23 2024

A326211 Number of unsortable normal multiset partitions of weight n.

Original entry on oeis.org

0, 0, 0, 1, 17, 170, 1455, 11678, 92871, 752473

Offset: 0

Gus Wiseman, Jun 19 2019

A multiset partition is normal if it covers an initial interval of positive integers. It is unsortable if no permutation has an ordered concatenation, or equivalently if the concatenation of its lexicographically-ordered parts is not weakly increasing. For example, the multiset partition {{1,2},{1,1,1},{2,2,2}} is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

			The a(3) = 1 and a(4) = 17 multiset partitions:
  {{1,3},{2}}  {{1,1,3},{2}}
               {{1,2},{1,2}}
               {{1,2},{1,3}}
               {{1,2,3},{2}}
               {{1,2,4},{3}}
               {{1,3},{2,2}}
               {{1,3},{2,3}}
               {{1,3},{2,4}}
               {{1,3,3},{2}}
               {{1,3,4},{2}}
               {{1,4},{2,3}}
               {{1},{1,3},{2}}
               {{1},{2,4},{3}}
               {{1,3},{2},{2}}
               {{1,3},{2},{3}}
               {{1,3},{2},{4}}
               {{1,4},{2},{3}}

Unsortable set partitions are A058681.
Sortable normal multiset partitions are A326212.
Non-crossing normal multiset partitions are A324171.
MM-numbers of unsortable multiset partitions are A326258.
Cf. A000108, A016098, A255906, A324170.
Cf. A326209, A326210, A326243, A326250, A326255, A326256.

lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
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[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[Select[Sort[#,lexsort]&/@Join@@mps/@allnorm[n],!OrderedQ[Join@@#]&]],{n,0,5}]

A255906(n) = a(n) + A326212(n).

A326256 MM-numbers of nesting multiset partitions.

Original entry on oeis.org

667, 989, 1334, 1633, 1769, 1817, 1978, 2001, 2021, 2323, 2461, 2623, 2668, 2967, 2987, 3197, 3266, 3335, 3538, 3634, 3713, 3749, 3956, 3979, 4002, 4042, 4171, 4331, 4379, 4429, 4439, 4577, 4646, 4669, 4747, 4819, 4859, 4899, 4922, 4945, 5029, 5246, 5267, 5307

Offset: 1

Gus Wiseman, Jun 20 2019

nonn

First differs from A326255 in lacking 2599.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is obtained by taking the multiset of prime indices of each prime index of n.
A multiset partition is nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x < z and t < y or z < x and y < t. This is a stronger condition than capturing, so for example {{1,3,5},{2,4}} is capturing but not nesting.

			The sequence of terms together with their multiset multisystems begins:
   667: {{2,2},{1,3}}
   989: {{2,2},{1,4}}
  1334: {{},{2,2},{1,3}}
  1633: {{2,2},{1,1,3}}
  1769: {{1,3},{1,2,2}}
  1817: {{2,2},{1,5}}
  1978: {{},{2,2},{1,4}}
  2001: {{1},{2,2},{1,3}}
  2021: {{1,4},{2,3}}
  2323: {{2,2},{1,6}}
  2461: {{2,2},{1,1,4}}
  2623: {{1,4},{1,2,2}}
  2668: {{},{},{2,2},{1,3}}
  2967: {{1},{2,2},{1,4}}
  2987: {{1,3},{2,2,2}}
  3197: {{2,2},{1,7}}
  3266: {{},{2,2},{1,1,3}}
  3335: {{2},{2,2},{1,3}}
  3538: {{},{1,3},{1,2,2}}
  3634: {{},{2,2},{1,5}}

MM-numbers of crossing multiset partitions are A324170.
MM-numbers of capturing multiset partitions are A326255.
Nesting set partitions are A016098.
Capturing set partitions are A326243.
Cf. A001055, A034827, A058681, A112798, A117662, A302242.
Cf. A326211, A326248, A326257, A326258, A326260.

nesXQ[stn_]:=MatchQ[stn,{_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;(xt)||(x>z&&yTable[PrimePi[p],{k}]]]];
Select[Range[10000],nesXQ[primeMS/@primeMS[#]]&]

A324167 Number of non-crossing antichain covers of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 9, 67, 633, 6763, 77766, 938957, 11739033, 150649945, 1973059212, 26265513030, 354344889798, 4833929879517, 66568517557803, 924166526830701, 12920482325488761, 181750521972603049, 2570566932237176232, 36532394627404815308, 521439507533582646156

Offset: 0

Gus Wiseman, Feb 17 2019

nonn

An antichain is non-crossing if no pair of distinct parts is of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The a(3) = 9 antichains:
  {{1,2,3}}
  {{1},{2,3}}
  {{2},{1,3}}
  {{3},{1,2}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1},{2},{3}}
  {{1,2},{1,3},{2,3}}

Andrew Howroyd, Table of n, a(n) for n = 0..500

Cf. A000108, A000124, A000372 (antichains), A001006, A006126 (antichain covers), A014466, A048143, A054726 (non-crossing graphs), A099947, A261005, A283877, A306438.

Cf. A324166, A324168, A324169, A324170, A324171, A324173, A359984 (no singletons).

nn=6;
croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

seq(n)={my(f=O(1)); for(n=2, n, f = 1 + (4*x + x^2)*f^2 - 3*x^2*(1 + x)*f^3); Vec(subst(x*(1 + x^2*f^2 - 3*x^3*f^3), x, x/(1-x))/x) } \\ Andrew Howroyd, Jan 20 2023

Inverse binomial transform of A324168.

Binomial transform of A359984. - Andrew Howroyd, Jan 20 2023

Terms a(9) and beyond from Andrew Howroyd, Jan 20 2023

A326258 MM-numbers of unsortable multiset partitions (with empty parts allowed).

Original entry on oeis.org

145, 169, 215, 290, 338, 355, 377, 395, 430, 435, 473, 481, 505, 507, 535, 559, 565, 580, 645, 667, 676, 695, 710, 725, 754, 790, 793, 803, 815, 841, 845, 860, 865, 869, 870, 905, 923, 946, 962, 965, 989, 995, 1010, 1014, 1015, 1027, 1065, 1070, 1073, 1075

Offset: 1

Gus Wiseman, Jun 22 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is obtained by taking the multiset of prime indices of each prime index of n.

A multiset partition is unsortable if no permutation has an ordered concatenation. For example, the multiset partition ((1,2),(1,1,1),(2,2,2)) is sortable because the permutation ((1,1,1),(1,2),(2,2,2)) has concatenation (1,1,1,1,2,2,2,2), which is weakly increasing.

			The sequence of terms together with their multiset multisystems begins:
  145: {{2},{1,3}}
  169: {{1,2},{1,2}}
  215: {{2},{1,4}}
  290: {{},{2},{1,3}}
  338: {{},{1,2},{1,2}}
  355: {{2},{1,1,3}}
  377: {{1,2},{1,3}}
  395: {{2},{1,5}}
  430: {{},{2},{1,4}}
  435: {{1},{2},{1,3}}
  473: {{3},{1,4}}
  481: {{1,2},{1,1,2}}
  505: {{2},{1,6}}
  507: {{1},{1,2},{1,2}}
  535: {{2},{1,1,4}}
  559: {{1,2},{1,4}}
  565: {{2},{1,2,3}}
  580: {{},{},{2},{1,3}}
  645: {{1},{2},{1,4}}
  667: {{2,2},{1,3}}

Unsortable set partitions are A058681.
Normal unsortable multiset partitions are A326211.
Unsortable digraphs are A326209.
MM-numbers of crossing multiset partitions are A324170.
MM-numbers of nesting multiset partitions are A326256.
MM-numbers of capturing multiset partitions are A326255.
Cf. A001055, A016098, A056239, A112798, A302242.
Cf. A326212, A326243, A326257, A326259.

lexsort[f_,c_]:=OrderedQ[PadRight[{f,c}]];
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],!OrderedQ[Join@@Sort[primeMS/@primeMS[#],lexsort]]&]

A324166 Number of totally crossing set partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 1, 1, 2, 6, 18, 57, 207, 842, 3673, 17062, 84897

Offset: 0

Gus Wiseman, Feb 17 2019

A set partition is totally crossing if every pair of distinct blocks is of the form {{...x...y...}, {...z...t...}} for some x < z < y < t or z < x < t < y.

			The a(6) = 18 totally crossing set partitions:
  {{1,2,3,4,5,6}}
  {{1,4,6},{2,3,5}}
  {{1,4,5},{2,3,6}}
  {{1,3,6},{2,4,5}}
  {{1,3,5},{2,4,6}}
  {{1,3,4},{2,5,6}}
  {{1,2,5},{3,4,6}}
  {{1,2,4},{3,5,6}}
  {{4,6},{1,2,3,5}}
  {{3,6},{1,2,4,5}}
  {{3,5},{1,2,4,6}}
  {{2,6},{1,3,4,5}}
  {{2,5},{1,3,4,6}}
  {{2,4},{1,3,5,6}}
  {{1,5},{2,3,4,6}}
  {{1,4},{2,3,5,6}}
  {{1,3},{2,4,5,6}}
  {{1,4},{2,5},{3,6}}

Cf. A000108 (non-crossing partitions), A000110, A000296, A002662, A016098 (crossing partitions), A054726, A099947 (topologically connected partitions), A305854, A306006, A306418, A306438, A319752.

Cf. A324170, A324171, A324172, A324173.

nn=6;
nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x

A324171 Number of non-crossing multiset partitions of normal multisets of size n.

Original entry on oeis.org

1, 1, 4, 16, 75, 378, 2042, 11489, 66697

Offset: 0

Gus Wiseman, Feb 17 2019

A multiset is normal if its union is an initial interval of positive integers.

A multiset partition is crossing if it has a 2-element submultiset of the form {{...x...y...}, {...z...t...}} where x < z < y < t or z < x < t < y.

			The A255906(5) - a(5) = 22 crossing multiset partitions:
  {{13}{124}}  {{1}{13}{24}}
  {{13}{224}}  {{1}{24}{35}}
  {{13}{234}}  {{2}{13}{24}}
  {{13}{244}}  {{2}{14}{35}}
  {{13}{245}}  {{3}{13}{24}}
  {{14}{235}}  {{3}{14}{25}}
  {{24}{113}}  {{4}{13}{24}}
  {{24}{123}}  {{4}{13}{25}}
  {{24}{133}}  {{5}{13}{24}}
  {{24}{134}}
  {{24}{135}}
  {{25}{134}}
  {{35}{124}}

Cf. A000108 (non-crossing set partitions), A000124, A001006, A001055, A001263, A007297, A054726 (non-crossing graphs), A099947, A194560, A255906 (multiset partitions of normal multisets), A306438.

Cf. A324166, A324167, A324168, A324169, A324170, A324173.

nonXQ[stn_]:=!MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
allnorm[n_]:=If[n<=0,{{}},Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1]];
Table[Sum[Length[Select[mps[m],nonXQ]],{m,allnorm[n]}],{n,0,8}]

A326255 MM-numbers of capturing multiset partitions.

Original entry on oeis.org

667, 989, 1334, 1633, 1769, 1817, 1978, 2001, 2021, 2323, 2461, 2599, 2623, 2668, 2967, 2987, 3197, 3266, 3335, 3538, 3634, 3713, 3749, 3956, 3979, 4002, 4042, 4163, 4171, 4331, 4379, 4429, 4439, 4577, 4646, 4669, 4747, 4819, 4859, 4899, 4922, 4945, 5029, 5198

Offset: 1

Gus Wiseman, Jun 20 2019

nonn

First differs from A326256 in having 2599.
A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798. The multiset multisystem with MM-number n is obtained by taking the multiset of prime indices of each prime index of n.
A multiset partition is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and t < y or z < x and y < t. This is a weaker condition than nesting, so for example {{1,3,5},{2,4}} is capturing but not nesting.

			The sequence of terms together with their multiset multisystems begins:
   667: {{2,2},{1,3}}
   989: {{2,2},{1,4}}
  1334: {{},{2,2},{1,3}}
  1633: {{2,2},{1,1,3}}
  1769: {{1,3},{1,2,2}}
  1817: {{2,2},{1,5}}
  1978: {{},{2,2},{1,4}}
  2001: {{1},{2,2},{1,3}}
  2021: {{1,4},{2,3}}
  2323: {{2,2},{1,6}}
  2461: {{2,2},{1,1,4}}
  2599: {{2,2},{1,2,3}}
  2623: {{1,4},{1,2,2}}
  2668: {{},{},{2,2},{1,3}}
  2967: {{1},{2,2},{1,4}}
  2987: {{1,3},{2,2,2}}
  3197: {{2,2},{1,7}}
  3266: {{},{2,2},{1,1,3}}
  3335: {{2},{2,2},{1,3}}
  3538: {{},{1,3},{1,2,2}}

MM-numbers of crossing multiset partitions are A324170.
MM-numbers of nesting multiset partitions are A326256.
MM-numbers of crossing capturing multiset partitions are A326259.
Capturing set partitions are A326243.
Cf. A001055, A034827, A058681, A112798, A117662, A122880, A302242.
Cf. A326211, A326249, A054391, A326257, A326258.

capXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;xt||x>z&&yTable[PrimePi[p],{k}]]]];
Select[Range[10000],capXQ[primeMS/@primeMS[#]]&]

cp's OEIS Frontend

A324173 Regular triangle read by rows where T(n,k) is the number of set partitions of {1,...,n} with k topologically connected components.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A326210 Number of labeled simple graphs with vertices {1..n} containing a nesting pair of edges, where two edges {a,b}, {c,d} are nesting if a < c and b > d or a > c and b < d.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326243 Number of capturing set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326211 Number of unsortable normal multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326256 MM-numbers of nesting multiset partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A324167 Number of non-crossing antichain covers of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326258 MM-numbers of unsortable multiset partitions (with empty parts allowed).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A324166 Number of totally crossing set partitions of {1,...,n}.

Views

Author