A324170 -id:A324170 - cp's OEIS frontend

A326248 Number of crossing, nesting set partitions of {1..n}.

0, 0, 0, 0, 0, 2, 28, 252, 1890, 13020, 86564, 571944, 3826230, 26233662, 185746860, 1364083084, 10410773076, 82609104802, 681130756224, 5829231836494, 51711093240518, 474821049202852, 4506533206814480, 44151320870760216, 445956292457725714

Offset: 0

Gus Wiseman, Jun 20 2019

nonn

A set partition is crossing if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < y < t or z < x < t < y, and nesting if it has two blocks of the form {...x,y...}, {...z,t...} where x < z < t < y or z < x < y < t.

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

Christian Sievers, Table of n, a(n) for n = 0..576

Crossing and nesting set partitions are (both) A016098.
Crossing, capturing set partitions are A326246.
Nesting, non-crossing set partitions are A122880.
Cf. A000108, A000110, A001519, A058681, A099947, A117662, A324170.
Cf. A326209, A326211, A326243, A326245, A326256, A326258.

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

a(n) = A000110(n) - 2*A000108(n) + A001519(n). - Christian Sievers, Oct 16 2024

a(11) and beyond from Christian Sievers, Oct 16 2024

A326212 Number of sortable normal multiset partitions of weight n.

Original entry on oeis.org

1, 1, 4, 15, 59, 230, 901, 3522, 13773, 53847, 210527, 823087, 3218002, 12581319, 49188823, 192312112, 751877137, 2939592383, 11492839729, 44933224559, 175674134309, 686828104551, 2685272063984, 10498530869151, 41045803846015, 160475597429847

Offset: 0

Gus Wiseman, Jun 19 2019

nonn

A multiset partition is normal if it covers an initial interval of positive integers. It is sortable if some 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 a(0) = 1 through a(3) = 15 multiset partitions:
  {}  {{1}}  {{1,1}}    {{1,1,1}}
             {{1,2}}    {{1,1,2}}
             {{1},{1}}  {{1,2,2}}
             {{1},{2}}  {{1,2,3}}
                        {{1},{1,1}}
                        {{1},{1,2}}
                        {{1,1},{2}}
                        {{1},{2,2}}
                        {{1,2},{2}}
                        {{1},{2,3}}
                        {{1,2},{3}}
                        {{1},{1},{1}}
                        {{1},{1},{2}}
                        {{1},{2},{2}}
                        {{1},{2},{3}}

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

Sortable set partitions are A011782.
Unsortable normal multiset partitions are A326211.
Crossing normal multiset partitions are A326277.
Cf. A000041, A000108, A058681, A255906, A324170, A324171.
Cf. A326209, A326237, A326255, A326256, A326257, A326258.

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}]

seq(n) = my(p=1/eta(x + O(x*x^n))); Vec(((1 - x)*(1 - 2*x) - x^2*p)/(2*(1 - x)*(1 - 2*x) - (1 - 3*x + 4*x^2)*p)) \\ Andrew Howroyd, May 11 2023

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

G.f.: ((1 - x)*(1 - 2*x) - x^2*P(x))/(2*(1 - x)*(1 - 2*x) - (1 - 3*x + 4*x^2)*P(x)) where P(x) is the g.f. of A000041. - Andrew Howroyd, May 11 2023

Terms a(10) and beyond from Andrew Howroyd, May 11 2023

A326257 MM-numbers of weakly nesting multiset partitions.

Original entry on oeis.org

49, 91, 98, 133, 147, 169, 182, 196, 203, 245, 247, 259, 266, 273, 294, 299, 301, 338, 343, 361, 364, 371, 377, 392, 399, 406, 427, 441, 455, 481, 490, 494, 497, 507, 518, 529, 532, 539, 546, 551, 553, 559, 588, 598, 602, 609, 623, 637, 665, 667, 676, 686, 689

Offset: 1

Gus Wiseman, Jun 21 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 weakly 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.

			The sequence of terms together with their multiset multisystems begins:
   49: {{1,1},{1,1}}
   91: {{1,1},{1,2}}
   98: {{},{1,1},{1,1}}
  133: {{1,1},{1,1,1}}
  147: {{1},{1,1},{1,1}}
  169: {{1,2},{1,2}}
  182: {{},{1,1},{1,2}}
  196: {{},{},{1,1},{1,1}}
  203: {{1,1},{1,3}}
  245: {{2},{1,1},{1,1}}
  247: {{1,2},{1,1,1}}
  259: {{1,1},{1,1,2}}
  266: {{},{1,1},{1,1,1}}
  273: {{1},{1,1},{1,2}}
  294: {{},{1},{1,1},{1,1}}
  299: {{1,2},{2,2}}
  301: {{1,1},{1,4}}
  338: {{},{1,2},{1,2}}
  343: {{1,1},{1,1},{1,1}}
  361: {{1,1,1},{1,1,1}}

MM-numbers of crossing multiset partitions are A324170.
MM-numbers of nesting multiset partitions are A324256.
MM-numbers of capturing multiset partitions are A326255.
Nesting set partitions are A016098.
Cf. A001055, A034827, A056239, A112798, A122880, A302242, A324171.
Cf. A326211, A326243, A326258, A326260.

wknXQ[stn_]:=MatchQ[stn,{_,{_,x_,y_,_},_,{_,z_,t_,_},_}/;(x<=z&&y>=t)||(x>=z&&y<=t)]
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[1000],wknXQ[primeMS/@primeMS[#]]&]

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

Original entry on oeis.org

1, 2, 5, 19, 120, 1084, 11783, 141110, 1791156, 23646352, 321220257, 4459886776, 63000867229, 902528825332, 13080523942476, 191445447535373, 2825542818304080, 42005234042942228, 628422035415996065, 9454076958795999908, 142933849346150225253, 2170556938059142024688

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(0) = 1 through a(3) = 19 non-crossing antichains:
  {}  {}     {}        {}
      {{1}}  {{1}}     {{1}}
             {{2}}     {{2}}
             {{12}}    {{3}}
             {{1}{2}}  {{12}}
                       {{13}}
                       {{23}}
                       {{123}}
                       {{1}{2}}
                       {{1}{3}}
                       {{2}{3}}
                       {{1}{23}}
                       {{2}{13}}
                       {{3}{12}}
                       {{12}{13}}
                       {{12}{23}}
                       {{13}{23}}
                       {{1}{2}{3}}
                       {{12}{13}{23}}

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

Cf. A000108 (non-crossing set partitions), A000124, A000372 (antichains), A001006, A001263, A006126 (antichain covers), A014466 (nonempty antichains), A054726 (non-crossing graphs), A099947, A261005, A306438.

Cf. A324166, A324167, A324169, A324170, A324171, A324173, A359984.

nn=6;
nonXQ[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-2*x))/x) } \\ Andrew Howroyd, Jan 20 2023

Binomial transform of A324167.

G.f.: A(x) = B(x/(1-2*x))/x where B(x)/x is the g.f. of A359984. - Andrew Howroyd, Jan 20 2023

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

A326246 Number of crossing, capturing set partitions of {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 0, 3, 37, 307, 2173, 14344, 92402, 596688

Offset: 0

Gus Wiseman, Jun 20 2019

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

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

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

MM-numbers of crossing, capturing multiset partitions are A326259.
Crossing set partitions are A016098.
Capturing set partitions are A326243.
Crossing, nesting set partitions are A326248.
Crossing, non-capturing set partitions are A326245.
Non-crossing, capturing set partitions are A122880 (conjecture).
Cf. A000108, A000110, A058681, A099947, A324170, A326211, A326249, A054391, A326255.

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

A324324 MM-numbers of crossing set partitions.

Original entry on oeis.org

2117, 3973, 4843, 5891, 6757, 7181, 7801, 10019, 10063, 11051, 11567, 13021, 13193, 13459, 14123, 14921, 17603, 18407, 18761, 18877, 19307, 19633, 20941, 21083, 21251, 21457, 22849, 23519, 23533, 24727, 26101, 27133, 27169, 27173, 27413, 29111, 30479, 31261

Offset: 1

Gus Wiseman, Feb 22 2019

nonn

A multiset multisystem is a finite multiset of finite multisets. 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 formed by taking the multiset of prime indices of each part in the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset multisystem with MM-number 78 is {{},{1},{1,2}}.

A multiset multisystem is crossing if it contains two parts of the form {{...x...y...},{...z...t...}} with x < z < y < t or z < x < t < y.

Cf. A000108 (non-crossing set partitions), A001055, A001222, A003963, A005117, A016098 (crossing set partitions), A054726, A056239, A112798, A302242, A302243, A302505, A302521 (MM-numbers of set partitions).

Cf. A324166, A324167, A324169, A324170, A324171, A324326.

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;xTable[PrimePi[p],{k}]]]];
setptnQ[bks_]:=UnsameQ@@Join@@bks&&!MemberQ[bks,{}];
Select[Range[10000],And[croXQ[primeMS/@primeMS[#]],setptnQ[primeMS/@primeMS[#]]]&]

A326252 Number of digraphs with vertices {1..n} whose increasing edges are crossing.

Original entry on oeis.org

0, 0, 0, 0, 16384, 22020096, 62679678976, 556181084962816

Offset: 0

Gus Wiseman, Jun 30 2019

A directed edge (a,b) is increasing if a < b. Two edges (a,b), (c,d) are crossing if a < c < b < d or c < a < d < b.

Simple graphs whose edges are crossing are A326210.
Digraphs whose increasing edges are not crossing are A326251.
Digraphs whose edges are not crossing are A326237.
Cf. A002416, A002720, A229865, A324170, A326209, A326252, A326258.

croXQ[eds_]:=MatchQ[eds,{_,{x_,y_},_,{z_,t_},_}/;x

a(n) = 2^(n * (n + 1)/2) * A326210(n).

A326259 MM-numbers of crossing, capturing multiset partitions (with empty parts allowed).

Original entry on oeis.org

8903, 15167, 16717, 17806, 18647, 20329, 20453, 21797, 22489, 25607, 26709, 27649, 29551, 30334, 31373, 32741, 33434, 34691, 35177, 35612, 35821, 37091, 37133, 37294, 37969, 38243, 39493, 40658, 40906, 41449, 42011, 42949, 43594, 43817, 43873, 44515, 44861

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 crossing if it has two blocks of the form {...x...y...}, {...z...t...} where x < z < y < t or z < x < t < y. It is capturing if it has two blocks of the form {...x...y...} and {...z...t...} where x < z and y > t or x > z and y < t. Capturing 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:
   8903: {{1,3},{2,2,4}}
  15167: {{1,3},{2,2,5}}
  16717: {{2,4},{1,3,3}}
  17806: {{},{1,3},{2,2,4}}
  18647: {{1,3},{2,2,6}}
  20329: {{1,3},{1,2,2,4}}
  20453: {{1,2,3},{1,2,4}}
  21797: {{1,1,3},{2,2,4}}
  22489: {{1,4},{2,2,5}}
  25607: {{1,3},{2,2,7}}
  26709: {{1},{1,3},{2,2,4}}
  27649: {{1,4},{2,2,6}}
  29551: {{1,3},{2,2,8}}
  30334: {{},{1,3},{2,2,5}}
  31373: {{2,5},{1,3,3}}
  32741: {{1,3},{2,2,2,4}}
  33434: {{},{2,4},{1,3,3}}
  34691: {{1,2,3},{2,2,4}}
  35177: {{1,3},{1,2,2,5}}
  35612: {{},{},{1,3},{2,2,4}}

Crossing set partitions are A000108.
Capturing set partitions are A326243.
Crossing, capturing set partitions are A326246.
MM-numbers of crossing multiset partitions are A324170.
MM-numbers of nesting multiset partitions are A326256.
MM-numbers of capturing multiset partitions are A326255.
MM-numbers of unsortable multiset partitions are A326258.
Cf. A001055, A001519, A016098, A056239, A058681, A112798, A122880, A302242.
Cf. A326211, A326245, A326248, A326249, A054391.

croXQ[stn_]:=MatchQ[stn,{_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;x_,{_,x_,_,y_,_},_,{_,z_,_,t_,_},_}/;xTable[PrimePi[p],{k}]]]];
Select[Range[100000],capXQ[primeMS/@primeMS[#]]&&croXQ[primeMS/@primeMS[#]]&]

A326279 Number of labeled n-vertex simple graphs containing either a crossing or a nesting pair of edges.

Original entry on oeis.org

0, 0, 0, 0, 28, 864, 32064, 2094064

Offset: 0

Gus Wiseman, Jun 23 2019

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b, and nesting if a < c < d < b or c < a < b < d.

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

Crossing and nesting simple graphs are (both) A326210, while non-crossing, non-nesting simple graphs are A326244.
Cf. A000108, A001519, A006125, A016098, A054726, A095661, A324170.
Cf. A326209, A326211, A326248, A326250, A326256.

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

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

A326245 Number of crossing, non-capturing set partitions of {1..n}.

Original entry on oeis.org

0, 0, 0, 0, 1, 7, 34, 141, 537, 1941, 6777, 23096, 77340

Offset: 0

Gus Wiseman, Jun 20 2019

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

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

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

Crossing set partitions are A016098.
Non-capturing set partitions are A054391.
Crossing, capturing set partitions are A326246.
Cf. A000108, A000110, A001519, A054391, A058681, A095661, A324170.
Cf. A326212, A326237, A326243, A326248, A326249.

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

cp's OEIS Frontend

A326248 Number of crossing, nesting set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326212 Number of sortable normal multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326257 MM-numbers of weakly nesting multiset partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A324168 Number of non-crossing antichains of nonempty subsets of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A326246 Number of crossing, capturing set partitions of {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A324324 MM-numbers of crossing set partitions.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A326252 Number of digraphs with vertices {1..n} whose increasing edges are crossing.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A326259 MM-numbers of crossing, capturing multiset partitions (with empty parts allowed).

Views

Author

Keywords

Comments