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

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,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..39.

Formula

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)

Example

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}

Mathematica

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

Crossrefs

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.

Sequence in context: A106598 A279128 A293038 * A014816 A147691 A000441

Adjacent sequences: A326275 A326276 A326277 * A326279 A326280 A326281

Keyword

nonn

Author

Gus Wiseman, Jun 23 2019

Status

approved