A326290 Number of non-crossing n-vertex graphs with loops.

1, 2, 8, 64, 768, 11264, 184320, 3227648, 59179008, 1121714176, 21803040768, 432218832896, 8705009516544, 177618573852672, 3663840373899264, 76277945940836352, 1600706475536154624, 33823752545680490496, 719051629204296695808, 15368152475218787434496

Offset

0,2

Comments

Two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b.

Links

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

Formula

From Andrew Howroyd, Sep 14 2019: (Start)

a(n) = 2^n * A054726(n).

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.

Cf. A000108, A002061, A002662, A054726, A324172, A326252.

Sequence in context: A268666 A193549 A005612 * A136282 A092934 A224801

Adjacent sequences: A326287 A326288 A326289 * A326291 A326292 A326293

Keyword

nonn

Author

Gus Wiseman, Sep 12 2019

Extensions

Terms a(6) and beyond from Andrew Howroyd, Sep 14 2019

Status

approved