cp's OEIS Frontend

A326278 Number of n-vertex, 2-edge multigraphs that are not nesting. Number of n-vertex, 2-edge multigraphs that are not crossing.

%I A326278 #6 Jun 25 2019 10:10:30
%S A326278 0,0,1,9,34,90,195,371,644,1044,1605,2365,3366,4654,6279,8295,10760,
%T A326278 13736,17289,21489,26410,32130,38731,46299,54924,64700,75725,88101,
%U A326278 101934,117334,134415,153295,174096,196944,221969,249305,279090,311466,346579,384579
%N A326278 Number of n-vertex, 2-edge multigraphs that are not nesting. Number of n-vertex, 2-edge multigraphs that are not crossing.
%C A326278 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.
%F A326278 Conjectures from _Colin Barker_, Jun 25 2019: (Start)
%F A326278 G.f.: x^2*(1 + 4*x - x^2) / (1 - x)^5.
%F A326278 a(n) = (n*(3 - 4*n + n^3)) / 6 .
%F A326278 a(n) = 5*a(n-1) - 10*a(n-2) + 10*a(n-3) - 5*a(n-4) + a(n-5) for n>4.
%F A326278 (End)
%e A326278 The a(3) = 9 non-crossing multigraphs:
%e A326278   {12,12}
%e A326278   {12,13}
%e A326278   {12,23}
%e A326278   {13,12}
%e A326278   {13,13}
%e A326278   {13,23}
%e A326278   {23,12}
%e A326278   {23,13}
%e A326278   {23,23}
%t A326278 croXQ[stn_]:=MatchQ[stn,{___,{x_,y_},___,{z_,t_},___}/;x<z<y<t||z<x<t<y];
%t A326278 Table[Length[Select[Tuples[Subsets[Range[n],{2}],2],!croXQ[#]&]],{n,0,10}]
%Y A326278 A326247(n) <= a(n) <= A000537(n).
%Y A326278 The case for 2-edge simple graphs (rather than multigraphs) is A117662.
%Y A326278 Cf. A000108, A001519, A006125, A016098, A054726, A095661.
%Y A326278 Cf. A326210, A326243, A326244, A326248, A326250.
%K A326278 nonn
%O A326278 0,4
%A A326278 _Gus Wiseman_, Jun 23 2019