login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=0..39.

FORMULA

Conjectures from Colin Barker, Jun 25 2019: (Start)

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

A326247(n) <= a(n) <= A000537(n).

The case for 2-edge simple graphs (rather than multigraphs) is A117662.

Cf. A000108, A001519, A006125, A016098, A054726, A095661.

Cf. A326210, A326243, A326244, A326248, A326250.

Sequence in context: A106598 A279128 A293038 * A014816 A147691 A000441

Adjacent sequences:  A326275 A326276 A326277 * A326279 A326280 A326281

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jun 23 2019

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 21 12:13 EDT 2020. Contains 337271 sequences. (Running on oeis4.)