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

Author

Gus Wiseman, Jun 20 2019

Keywords

• nonn

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.

Examples

			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}
		

Links

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

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.

Programs

Mathematica

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

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)