login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A326247 Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting. 2
0, 0, 1, 9, 32, 80, 165, 301, 504, 792, 1185, 1705, 2376, 3224, 4277, 5565, 7120, 8976, 11169, 13737, 16720, 20160, 24101, 28589, 33672, 39400, 45825, 53001, 60984, 69832, 79605, 90365, 102176, 115104, 129217, 144585, 161280, 179376, 198949, 220077, 242840 (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..40.

Gus Wiseman, The a(4) = 32 pairs of edges that are neither crossing nor nesting.

FORMULA

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

G.f.: x^2*(1 + 4*x - 3*x^2) / (1 - x)^5.

a(n) = (n*(12 - 19*n + 6*n^2 + n^3)) / 12.

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 pairs of edges:

  {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];

nestQ[stn_]:=MatchQ[stn, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<t<y||z<x<y<t];

Table[Length[Select[Tuples[Subsets[Range[n], {2}], 2], !nesXQ[#]&&!croXQ[#]&]], {n, 0, 10}]

CROSSREFS

The case for simple graphs (rather than multigraphs) is A095661.

Simple graphs that are neither crossing nor nesting are A326244.

The case for set partitions is A001519.

Non-crossing and non-nesting simple graphs are (both) A054726.

Cf. A000108, A002061, A006125, A117662, A324170, A326250, A326256.

Sequence in context: A027620 A152619 A051662 * A225918 A231999 A297298

Adjacent sequences:  A326244 A326245 A326246 * A326248 A326249 A326250

KEYWORD

nonn

AUTHOR

Gus Wiseman, Jun 20 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 October 22 17:34 EDT 2019. Contains 328319 sequences. (Running on oeis4.)