|
%I #8 Jun 21 2019 22:45:08
%S 0,0,1,9,32,80,165,301,504,792,1185,1705,2376,3224,4277,5565,7120,
%T 8976,11169,13737,16720,20160,24101,28589,33672,39400,45825,53001,
%U 60984,69832,79605,90365,102176,115104,129217,144585,161280,179376,198949,220077,242840
%N Number of labeled n-vertex 2-edge multigraphs that are neither crossing nor nesting.
%C 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.
%H Gus Wiseman, <a href="/A326247/a326247.png">The a(4) = 32 pairs of edges that are neither crossing nor nesting</a>.
%F Conjectures from _Colin Barker_, Jun 21 2019: (Start)
%F G.f.: x^2*(1 + 4*x - 3*x^2) / (1 - x)^5.
%F a(n) = (n*(12 - 19*n + 6*n^2 + n^3)) / 12.
%F 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 (End)
%e The a(3) = 9 pairs of edges:
%e {12,12}
%e {12,13}
%e {12,23}
%e {13,12}
%e {13,13}
%e {13,23}
%e {23,12}
%e {23,13}
%e {23,23}
%t croXQ[stn_]:=MatchQ[stn,{___,{x_,y_},___,{z_,t_},___}/;x<z<y<t||z<x<t<y];
%t nestQ[stn_]:=MatchQ[stn,{___,{x_,y_},___,{z_,t_},___}/;x<z<t<y||z<x<y<t];
%t Table[Length[Select[Tuples[Subsets[Range[n],{2}],2],!nesXQ[#]&&!croXQ[#]&]],{n,0,10}]
%Y The case for simple graphs (rather than multigraphs) is A095661.
%Y Simple graphs that are neither crossing nor nesting are A326244.
%Y The case for set partitions is A001519.
%Y Non-crossing and non-nesting simple graphs are (both) A054726.
%Y Cf. A000108, A002061, A006125, A117662, A324170, A326250, A326256.
%K nonn
%O 0,4
%A _Gus Wiseman_, Jun 20 2019
|
