login
A326247
Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting.
2
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.
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.
Sequence in context: A027620 A152619 A051662 * A362526 A225918 A367669
KEYWORD
nonn
AUTHOR
Gus Wiseman, Jun 20 2019
STATUS
approved