A326250 -id:A326250 - 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

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

A326244 Number of labeled n-vertex simple graphs without crossing or nesting edges.

Original entry on oeis.org

1, 1, 2, 8, 36, 160, 704, 3088, 13536, 59328, 260032, 1139712

Offset: 0

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

Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
Gus Wiseman, The a(4) = 36 non-crossing, non-nesting simple labeled graphs.

The case for set partitions is A001519.
Simple graphs with crossing or nesting edges are A326279.
Cf. A000088, A000108, A006125, A016098, A054726, A095661, A117662.
Cf. A326209, A326210, A326250, A326255, A326256.

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

A006125(n) = a(n) + A326279(n).
Conjectures from Colin Barker, Jun 28 2019: (Start)
G.f.: (1 - x)*(1 - 4*x) / (1 - 6*x + 8*x^2 - 4*x^3).
a(n) = 6*a(n-1) - 8*a(n-2) + 4*a(n-3) for n>2.
(End)

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

A326237 Number of non-nesting digraphs with vertices {1..n}, 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

1, 2, 12, 104, 1008, 10272, 107712, 1150592

Offset: 0

Gus Wiseman, Jun 19 2019

These are digraphs with the property that, if the edges are listed in lexicographic order, the sequence of targets is weakly increasing. For example, the digraph with lexicographically ordered edge set {(1,2),(2,1),(3,1),(3,2)} is nesting because the targets are (2,1,1,2), a sequence that is not weakly increasing.
Also the number of non-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 non-semicrossing digraph edge-sets are:
  {}
  {11}
  {12}
  {21}
  {22}
  {11,12}
  {11,21}
  {12,21}
  {12,22}
  {21,22}
  {11,12,21}
  {12,21,22}
Apparently a duplicate of A152254. - R. J. Mathar, Jul 12 2019

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

Nesting digraphs are A326209.
Non-nesting set partitions are A000108.
Non-capturing set partitions are A054391.
Cf. A002416, A002720, A054391, A058681, A122880, A229865.
Cf. A326249, A326250, A326251, A326256, A326257.

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

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

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

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

Original entry on oeis.org

1, 2, 16, 512, 49152, 11534336, 6039797760, 6768868458496, 15885743998107648, 77083611222073409536, 767126299049285413502976, 15572324598183490228037091328, 642316330843573124053884695740416, 53681919993405760099480940765478125568

Offset: 0

Gus Wiseman, Jun 30 2019

nonn

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.

Conjecture: Also the number of non-nesting digraphs with vertices {1..n} whose increasing edges are not crossing, where two edges (a,b), (c,d) are nesting if a < c < d < b or c < a < b < d.

Simple graphs whose edges are non-crossing are A054726.
Digraphs whose edges are not crossing are A326237.
Digraphs whose increasing edges are crossing are A326252.
Cf. A002416, A229865, A324170, A326209, A326250, A326251.

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

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

A326247 Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting.

Original entry on oeis.org

0, 0, 1, 9, 32, 80, 165, 301, 504, 792, 1185, 1705, 2376, 3224, 4277, 5565, 7120, 8976, 11169, 13737, 16720, 20160, 24101, 28589, 33672, 39400, 45825, 53001, 60984, 69832, 79605, 90365, 102176, 115104, 129217, 144585, 161280, 179376, 198949, 220077, 242840

Offset: 0

Gus Wiseman, Jun 20 2019

nonn

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(3) = 9 pairs of edges:
  {12,12}
  {12,13}
  {12,23}
  {13,12}
  {13,13}
  {13,23}
  {23,12}
  {23,13}
  {23,23}

Gus Wiseman, The a(4) = 32 pairs of edges that are neither crossing nor nesting.

The case for simple graphs (rather than multigraphs) is A095661.
Simple graphs that are neither crossing nor nesting are A326244.
The case for set partitions is A001519.
Non-crossing and non-nesting simple graphs are (both) A054726.
Cf. A000108, A002061, A006125, A117662, A324170, A326250, A326256.

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

Conjectures from Colin Barker, Jun 21 2019: (Start)
G.f.: x^2*(1 + 4*x - 3*x^2) / (1 - x)^5.
a(n) = (n*(12 - 19*n + 6*n^2 + n^3)) / 12.
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>4.
(End)

A326289 a(0) = 0, a(n) = 2^binomial(n,2) - 2^(n - 1).

Original entry on oeis.org

0, 0, 0, 4, 56, 1008, 32736, 2097088, 268435328, 68719476480, 35184372088320, 36028797018962944, 73786976294838204416, 302231454903657293672448, 2475880078570760549798240256, 40564819207303340847894502555648, 1329227995784915872903807060280311808

Offset: 0

Gus Wiseman, Jun 23 2019

nonn

Number of simple graphs with vertices {1..n} containing two edges {a,b}, {c,d} that are weakly crossing, meaning a <= c < b <= d or c <= a < d <= b.

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

Cf. A000088, A000108, A002662, A006125, A016098, A054726, A324170.

Cf. A326210, A326244, A326248, A326250, A326257, A326279, A326290.

Table[If[n==0,0,2^Binomial[n,2]-2^(n-1)],{n,0,5}]

A326278 Number of n-vertex, 2-edge multigraphs that are not nesting. Number of n-vertex, 2-edge multigraphs that are not crossing.

Original entry on oeis.org

0, 0, 1, 9, 34, 90, 195, 371, 644, 1044, 1605, 2365, 3366, 4654, 6279, 8295, 10760, 13736, 17289, 21489, 26410, 32130, 38731, 46299, 54924, 64700, 75725, 88101, 101934, 117334, 134415, 153295, 174096, 196944, 221969, 249305, 279090, 311466, 346579, 384579

Offset: 0

Gus Wiseman, Jun 23 2019

nonn

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(3) = 9 non-crossing multigraphs:
  {12,12}
  {12,13}
  {12,23}
  {13,12}
  {13,13}
  {13,23}
  {23,12}
  {23,13}
  {23,23}

A326247(n) <= a(n) <= A000537(n).
The case for 2-edge simple graphs (rather than multigraphs) is A117662.
Cf. A000108, A001519, A006125, A016098, A054726, A095661.
Cf. A326210, A326243, A326244, A326248, A326250.

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

Conjectures from Colin Barker, Jun 25 2019: (Start)
G.f.: x^2*(1 + 4*x - x^2) / (1 - x)^5.
a(n) = (n*(3 - 4*n + n^3)) / 6 .
a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>4.
(End)

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

A326211 Number of unsortable normal multiset partitions of weight n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326244 Number of labeled n-vertex simple graphs without crossing or nesting edges.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A326237 Number of non-nesting digraphs with vertices {1..n}, 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

Crossrefs

Programs

Mathematica

Formula

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

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

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A326247 Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting.

Views

Author

Keywords

Comments

Examples

Links