|
|
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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
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
|
The case for 2-edge simple graphs (rather than multigraphs) is A117662.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|