A326248 -id:A326248 - cp's OEIS frontend

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.

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

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[#]]&]

A326209 Number of nesting labeled digraphs with vertices {1..n}.

Original entry on oeis.org

0, 0, 4, 408, 64528

Offset: 0

Gus Wiseman, Jun 19 2019

Two edges (a,b), (c,d) are nesting if a < c and b > d or a > c and b < d.
Also unsortable digraphs with vertices {1..n}, where a digraph is sortable if, when the edges are listed in lexicographic order, their targets are weakly increasing.
Also the number of semicrossing digraphs with vertices {1..n}, where two edges (a,b), (c,d) are semicrossing if a < c and b < d or a > c and b > d. For example, the a(2) = 4 semicrossing digraph edge-sets are:
  {11,22}
  {11,12,22}
  {11,21,22}
  {11,12,21,22}

			The a(2) = 4 nesting digraph edge-sets:
  {12,21}
  {11,12,21}
  {12,21,22}
  {11,12,21,22}

Non-nesting digraphs are A326237.
Nesting set partitions are A016098.
MM-numbers of nesting multiset partitions are A326256.
MM-numbers of unsortable multiset partitions are A326258.
Cf. A000108, A001519, A002416, A229865.
Cf. A326210, A326211, A326243, A326246, A326248, A326250.

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

A002416(n) = a(n) + A326237(n).

A326250 Number of weakly nesting simple graphs with vertices {1..n}.

Original entry on oeis.org

0, 0, 0, 3, 50, 982, 32636, 2096723

Offset: 0

Gus Wiseman, Jun 21 2019

Two edges {a,b}, {c,d} are weakly nesting if a <= c < d <= b or c <= a < b <= d.

Gus Wiseman, The a(4) = 50 weakly nesting simple graphs.

Non-nesting set partitions are A000108.
Non-crossing graphs are A054726.
Nesting digraphs are A326209.
Crossing graphs are A326210.
MM-numbers of nesting multiset partitions are A326256.
Cf. A000088, A000332, A006125, A117662.
Cf. A326211, A326243, A326244, A326248, A326257, A326279.

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

Conjecture: A006125(n) = a(n) + A000108(n).

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

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

A326335 Number of set partitions of {1..n} whose nesting blocks are connected.

Original entry on oeis.org

1, 1, 1, 1, 2, 6, 21, 86, 394, 1974, 10696

Offset: 0

Gus Wiseman, Jun 27 2019

Two blocks are nesting if they are of the form {...x,y...}, {...z,t...} where x < z < t < y or z < x < y < t. A set partition has its nesting blocks connected if the graph whose vertices are the blocks and whose edges are nesting pairs of blocks is connected.

			The a(0) = 1 through a(6) = 21 set partitions:
  {}  {1}  {12}  {123}  {1234}    {12345}    {123456}
                        {14}{23}  {125}{34}  {1236}{45}
                                  {134}{25}  {1245}{36}
                                  {14}{235}  {125}{346}
                                  {145}{23}  {1256}{34}
                                  {15}{234}  {126}{345}
                                             {134}{256}
                                             {1345}{26}
                                             {1346}{25}
                                             {136}{245}
                                             {14}{2356}
                                             {145}{236}
                                             {1456}{23}
                                             {146}{235}
                                             {15}{2346}
                                             {156}{234}
                                             {16}{2345}
                                             {15}{26}{34}
                                             {16}{23}{45}
                                             {16}{24}{35}
                                             {16}{25}{34}

Simple graphs whose nesting blocks are connected are A326330.
Set partitions whose crossing blocks are connected are A099947.
Set partitions whose capturing blocks are connected are A326336.
Cf. A000110, A001519, A016098, A122880, A324173, A326243, A326248, A326293, A326331, A326337.

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

A326336 Number of set partitions of {1..n} whose capturing blocks are connected.

Original entry on oeis.org

1, 1, 1, 1, 2, 7, 24, 100, 458, 2279, 12270

Offset: 0

Gus Wiseman, Jun 28 2019

Two blocks are capturing if they are of the form {...x...y...}, {...z...t...} where x < z < t < y or z < x < y < t. A set partition has its capturing blocks connected if the graph whose vertices are the blocks and whose edges are capturing pairs of blocks is connected.

			The a(0) = 1 through a(6) = 24 set partitions:
  {}  {1}  {12}  {123}  {1234}    {12345}    {123456}
                        {14}{23}  {125}{34}  {1236}{45}
                                  {134}{25}  {1245}{36}
                                  {135}{24}  {1246}{35}
                                  {14}{235}  {125}{346}
                                  {145}{23}  {1256}{34}
                                  {15}{234}  {126}{345}
                                             {134}{256}
                                             {1345}{26}
                                             {1346}{25}
                                             {135}{246}
                                             {1356}{24}
                                             {136}{245}
                                             {14}{2356}
                                             {145}{236}
                                             {1456}{23}
                                             {146}{235}
                                             {15}{2346}
                                             {156}{234}
                                             {16}{2345}
                                             {15}{26}{34}
                                             {16}{23}{45}
                                             {16}{24}{35}
                                             {16}{25}{34}

Simple graphs whose capturing blocks are connected are A326330.
Set partitions whose crossing blocks are connected are A099947.
Set partitions whose nesting blocks are connected are A326335.
Cf. A000110, A001519, A016098, A122880, A324173, A326243, A326248, A326293, A326331, A326337.

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

cp's OEIS Frontend

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

A326256 MM-numbers of nesting multiset partitions.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A326209 Number of nesting labeled digraphs with vertices {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326250 Number of weakly nesting simple graphs with vertices {1..n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs