|
|
A326290
|
|
Number of non-crossing n-vertex graphs with loops.
|
|
2
|
|
|
1, 2, 8, 64, 768, 11264, 184320, 3227648, 59179008, 1121714176, 21803040768, 432218832896, 8705009516544, 177618573852672, 3663840373899264, 76277945940836352, 1600706475536154624, 33823752545680490496, 719051629204296695808, 15368152475218787434496
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: 1 + 3*x - 4*x^2 - x*sqrt(1 - 24*x + 16*x^2). (End)
|
|
EXAMPLE
|
The a(0) = 1 through a(2) = 8 non-crossing edge sets with loops:
{} {} {}
{11} {11}
{12}
{22}
{11,12}
{11,22}
{12,22}
{11,12,22}
|
|
MATHEMATICA
|
croXQ[stn_]:=MatchQ[stn, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<t<y||z<x<y<t];
Table[Length[Select[Subsets[Select[Tuples[Range[n], 2], OrderedQ]], !croXQ[#]&]], {n, 0, 5}]
|
|
PROG
|
(PARI) seq(n)=Vec(1+3*x-4*x^2 -x*sqrt(1-24*x+16*x^2 + O(x^n))) \\ Andrew Howroyd, Sep 14 2019
|
|
CROSSREFS
|
Crossing and nesting simple graphs are (both) A326210, while non-crossing, non-nesting simple graphs are A326244.
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|