A117662 -id:A117662 - cp's OEIS frontend

A326294 Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.

1, 1, 2, 8, 35, 147, 600, 2418

Offset: 0

Gus Wiseman, Jun 29 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) = 35 edge-sets:
  {}  {12}  {12,13}  {12,13,14}  {12,13,14,34}
      {13}  {12,14}  {12,13,23}  {12,13,23,34}
      {14}  {12,23}  {12,13,34}  {12,14,24,34}
      {23}  {12,24}  {12,14,24}  {12,23,24,34}
      {24}  {13,14}  {12,14,34}
      {34}  {13,23}  {12,23,24}
            {13,34}  {12,23,34}
            {14,24}  {12,24,34}
            {14,34}  {13,14,34}
            {23,24}  {13,23,34}
            {23,34}  {14,24,34}
            {24,34}  {23,24,34}

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

The inverse binomial transform is the covering case A326339.
Covering graphs with no crossing or nesting edges are A326329.
Connected simple graphs are A001349.
Graphs without crossing or nesting edges are A326244.
Cf. A006125, A054726, A117662, A136653.
Cf. A324169, A326210, A326293, A326340.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[csm[#]]<=1&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

Conjecture: a(n) = A052161(n - 2) + 1.

A129367 Triangle T(n, k) = A002415(n-k+3)*A002415(k+3), read by rows.

Original entry on oeis.org

36, 120, 120, 300, 400, 300, 630, 1000, 1000, 630, 1176, 2100, 2500, 2100, 1176, 2016, 3920, 5250, 5250, 3920, 2016, 3240, 6720, 9800, 11025, 9800, 6720, 3240, 4950, 10800, 16800, 20580, 20580, 16800, 10800, 4950, 7260, 16500, 27000, 35280, 38416, 35280, 27000, 16500, 7260

Offset: 0

Roger L. Bagula and Gary W. Adamson, Aug 25 2008

			Triangle begins as:
    36;
   120,   120;
   300,   400,   300;
   630,  1000,  1000,   630;
  1176,  2100,  2500,  2100,  1176;
  2016,  3920,  5250,  5250,  3920,  2016;
  3240,  6720,  9800, 11025,  9800,  6720,  3240;
  4950, 10800, 16800, 20580, 20580, 16800, 10800,  4950;
  7260, 16500, 27000, 35280, 38416, 35280, 27000, 16500, 7260;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A002415, A117662.

[Binomial((n-k+3)^2,2)*Binomial((k+3)^2,2)/36: k in [0..n], n in [0..12]]; // G. C. Greubel, Jan 31 2024

A129367[n_, k_]:= Binomial[(n-k+3)^2, 2]*Binomial[(k+3)^2, 2]/36;
Table[A129367[n,k], {n,0,12}, {k,0,n}]//Flatten

def A129367(n,k): return binomial((n-k+3)^2,2)*binomial((k+3)^2,2)/36
flatten([[A129367(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Jan 31 2024

T(n,k) = A002415(n-k+3)*A002415(k+3), where A002415(n) = n^2*(n^2-1)/12.

T(n, n-k) = T(n, k).

Edited by G. C. Greubel, Jan 31 2024

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)

A326349 Number of non-nesting, topologically connected simple graphs covering {1..n}.

Original entry on oeis.org

1, 0, 1, 0, 1, 11, 95, 797

Offset: 0

Gus Wiseman, Jun 30 2019

Covering means there are no isolated vertices. 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. A graph with positive integer vertices is topologically connected if the graph whose vertices are the edges and whose edges are crossing pairs of edges is connected.

			The a(5) = 11 edge-sets:
  {13,14,25}
  {13,24,25}
  {13,24,35}
  {14,24,35}
  {14,25,35}
  {13,14,24,25}
  {13,14,24,35}
  {13,14,25,35}
  {13,24,25,35}
  {14,24,25,35}
  {13,14,24,25,35}

Gus Wiseman, The a(6) = 95 non-nesting, topologically connected, covering simple graphs.

The binomial transform is the non-covering case A326293.
Topologically connected, covering simple graphs are A324327.
Non-crossing, covering simple graphs are A324169.
Cf. A000108, A000699, A006125, A054726, A099947, A117662.
Cf. A324323, A324328, A326329, A326330, A326339, A326341.

croXQ[eds_]:=MatchQ[eds,{_,{x_,y_},_,{z_,t_},_}/;x_,{x_,y_},_,{z_,t_},_}/;x0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&!nesXQ[#]&&Length[csm[Union[Subsets[#,{1}],Select[Subsets[#,{2}],croXQ]]]]<=1&]],{n,0,5}]

A326350 Number of non-nesting connected simple graphs with vertices {1..n}.

Original entry on oeis.org

1, 0, 1, 4, 23, 157, 1182

Offset: 0

Gus Wiseman, Jun 30 2019

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

Gus Wiseman, The a(4) = 23 non-nesting connected simple graphs.
Gus Wiseman, The a(5) = 157 non-nesting connected simple graphs.

The inverse binomial transform is the non-covering case A326351.
Connected simple graphs are A001349.
Connected simple graphs with no crossing or nesting edges are A326294.
Simple graphs without crossing or nesting edges are A326244.
Cf. A006125, A054726, A117662, A136653.
Cf. A324169, A326210, A326293, A326329, A326340.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#==Range[n]&&Length[csm[#]]<=1&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A130857 a(n) = (n-1)n(n+1)(n+2)(2n+11)/120.

Original entry on oeis.org

0, 3, 17, 57, 147, 322, 630, 1134, 1914, 3069, 4719, 7007, 10101, 14196, 19516, 26316, 34884, 45543, 58653, 74613, 93863, 116886, 144210, 176410, 214110, 257985, 308763, 367227, 434217, 510632, 597432, 695640, 806344, 930699, 1069929

Offset: 1

Roger L. Bagula, Jul 22 2007

nonn

The motivation for this sequence is the triple sum Sum[Sum[Sum[k^2-1,{k,1,m}],{m,1,j}],{j,1,n}], which can be simplified into the polynomial term given as definition.

Cf. A117662.

Table[(n - 1)*n(n + 1)*(n + 2)*(2*n + 11)/120, {n, 1, 35}]
Times@@#*(2#[[2]]+11)/120&/@Partition[Range[0,40],4,1] (* Harvey P. Dale, Oct 28 2012 *)

G.f.: -x^2*(x-3)/(-1+x)^6. - R. J. Mathar, Nov 14 2007

Edited and extended by N. J. A. Sloane, Jul 26 2007

A326351 Number of non-nesting connected simple graphs on a subset of {1..n}.

Original entry on oeis.org

1, 1, 2, 8, 46, 323, 2565

Offset: 0

Gus Wiseman, Jun 30 2019

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

The binomial transform is the covering case A326350.
Connected simple graphs are A001349.
Connected simple graphs with no crossing or nesting edges are A326294.
Simple graphs without crossing or nesting edges are A326244.
Cf. A006125, A054726, A117662, A136653.
Cf. A324169, A326210, A326293, A326329, A326340.

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[csm[#]]<=1&&!MatchQ[#,{_,{x_,y_},_,{z_,t_},_}/;x

A211381 Number of pairs of intersecting diagonals in the exterior of a regular n-gon.

Original entry on oeis.org

0, 0, 0, 0, 7, 24, 63, 130, 242, 408, 650, 980, 1425, 2000, 2737, 3654, 4788, 6160, 7812, 9768, 12075, 14760, 17875, 21450, 25542, 30184, 35438, 41340, 47957, 55328, 63525, 72590, 82600, 93600, 105672, 118864, 133263, 148920, 165927, 184338, 204250, 225720

Offset: 3

Martin Renner, Feb 07 2013

Eric Weisstein's World of Mathematics, Regular Polygon Division by Diagonals.
Index entries for linear recurrences with constant coefficients, signature (3,-1,-5,5,1,-3,1).

Cf. A000332, A117662, A176145, A211380.

a:= n-> `if`(n mod 2 = 0, 1/24*n*(n-4)*(n-6)*(2*n-7), 1/24*n*(n-3)*(n-5)*(2*n-11)): seq (a(n), n=3..40);

a(n) = 1/24*n*(n-4)*(n-6)*(2*n-7) for n even.
a(n) = 1/24*n*(n-3)*(n-5)*(2*n-11) for n odd.
a(n) = A211380(n) - A000332(n).
G.f.: x^7*(2*x^2-3*x-7) / ((x-1)^5*(x+1)^2). [Colin Barker, Feb 14 2013]

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

A326294 Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A129367 Triangle T(n, k) = A002415(n-k+3)*A002415(k+3), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A326349 Number of non-nesting, topologically connected simple graphs covering {1..n}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A326350 Number of non-nesting connected simple graphs with vertices {1..n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

A130857 a(n) = (n-1)*n*(n+1)*(n+2)*(2n+11)/120.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A326351 Number of non-nesting connected simple graphs on a subset of {1..n}.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A211381 Number of pairs of intersecting diagonals in the exterior of a regular n-gon.

Views

Author

Keywords

Links

Crossrefs

Programs

A130857 a(n) = (n-1)n(n+1)(n+2)(2n+11)/120.