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

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,4

Comments

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.

Links

Table of n, a(n) for n=0..40.

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

Formula

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)

Example

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}

Mathematica

croXQ[stn_]:=MatchQ[stn, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<y<t||z<x<t<y];
nestQ[stn_]:=MatchQ[stn, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<t<y||z<x<y<t];
Table[Length[Select[Tuples[Subsets[Range[n], {2}], 2], !nesXQ[#]&&!croXQ[#]&]], {n, 0, 10}]

Crossrefs

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.

Sequence in context: A027620 A152619 A051662 * A362526 A225918 A367669

Adjacent sequences: A326244 A326245 A326246 * A326248 A326249 A326250

Keyword

nonn

Author

Gus Wiseman, Jun 20 2019

Status

approved