|
|
A326244
|
|
Number of labeled n-vertex simple graphs without crossing or nesting edges.
|
|
18
|
|
|
1, 1, 2, 8, 36, 160, 704, 3088, 13536, 59328, 260032, 1139712
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
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.: (1 - x)*(1 - 4*x) / (1 - 6*x + 8*x^2 - 4*x^3).
a(n) = 6*a(n-1) - 8*a(n-2) + 4*a(n-3) for n>2.
(End)
|
|
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[Subsets[Subsets[Range[n], {2}]], !croXQ[#]&&!nestQ[#]&]], {n, 0, 5}]
|
|
CROSSREFS
|
The case for set partitions is A001519.
Simple graphs with crossing or nesting edges are A326279.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|