A324169 Number of labeled graphs covering the vertex set {1,...,n} with no crossing edges.

1, 0, 1, 4, 25, 176, 1353, 11012, 93329, 815104, 7285489, 66324644, 612863337, 5733381616, 54195878137, 516852285668, 4966883732129, 48049936644736, 467566946973537, 4573486005681092, 44942852084894777, 443484037981300144, 4392621673072766505

Offset

0,4

Comments

Two edges {x,y}, {z,t} are crossing if either x < z < y < t or z < x < t < y. If the vertices are arranged in a circle, this is equivalent to crossing of chords.

Covering means there are no isolated vertices.

Links

Andrew Howroyd, Table of n, a(n) for n = 0..500

Gus Wiseman, The a(4) = 25 graphs covering {1,2,3,4} with no crossing edges.

Gus Wiseman, The a(5) = 176 graphs covering 5 vertices with no crossing edges, radial embedding.

Formula

Inverse binomial transform of A054726.

G.f.: (2 + 7*x + 3*x^2 - x*sqrt(1 - 10*x - 7*x^2))/(2*(1 + x)^3). - Andrew Howroyd, Jan 20 2023

Mathematica

nn=8;
croXQ[stn_]:=MatchQ[stn, {___, {___, x_, ___, y_, ___}, ___, {___, z_, ___, t_, ___}, ___}/; x<z<y<t||z<x<t<y];
stableSets[u_, Q_]:=If[Length[u]===0, {{}}, With[{w=First[u]}, Join[stableSets[DeleteCases[u, w], Q], Prepend[#, w]&/@stableSets[DeleteCases[u, r_/; r===w||Q[r, w]||Q[w, r]], Q]]]];
Table[Length[Select[stableSets[Subsets[Range[n], {2}], croXQ[{#1, #2}]&], Union@@#==Range[n]&]], {n, 0, nn}]

Prog

(PARI) seq(n)=Vec((2 + 7*x + 3*x^2 - x*sqrt(1 - 10*x - 7*x^2 + O(x^n)))/(2*(1 + x)^3)) \\ Andrew Howroyd, Jan 20 2023

Crossrefs

Cf. A000108, A000124, A001006, A001764, A003465, A007297 (connected case), A016098, A054726 (non-crossing graphs), A099947, A306438.

Cf. A324167, A324171, A324173.

Sequence in context: A006348 A213608 A369325 * A213231 A051820 A362206

Adjacent sequences: A324166 A324167 A324168 * A324170 A324171 A324172

Keyword

nonn

Author

Gus Wiseman, Feb 17 2019

Status

approved