

A326210


Number of labeled simple graphs with vertices {1..n} containing a nesting pair of edges, where two edges {a,b}, {c,d} are nesting if a < c and b > d or a > c and b < d.


20



0, 0, 0, 0, 16, 672, 29888, 2071936, 268204288, 68717285888, 35184350796800, 36028796807919616, 73786976292712960000, 302231454903635611721728, 2475880078570760326175178752, 40564819207303340845566684397568, 1329227995784915872903782635437883392
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

Also simple graphs containing a crossing pair of edges, where two edges {a,b}, {c,d} are crossing if a < c < b < d or c < a < d < b.
Also simple graphs such that, if the edges are listed in lexicographic order, their maxima (seconds) are not weakly increasing.


LINKS



FORMULA



EXAMPLE

The a(4) = 16 nesting edgesets:
{14,23}
{12,14,23}
{13,14,23}
{14,23,24}
{14,23,34}
{12,13,14,23}
{12,14,23,24}
{12,14,23,34}
{13,14,23,24}
{13,14,23,34}
{14,23,24,34}
{12,13,14,23,24}
{12,13,14,23,34}
{12,14,23,24,34}
{13,14,23,24,34}
{12,13,14,23,24,34}
The a(4) = 16 crossing edgesets:
{13,24}
{12,13,24}
{13,14,24}
{13,23,24}
{13,24,34}
{12,13,14,24}
{12,13,23,24}
{12,13,24,34}
{13,14,23,24}
{13,14,24,34}
{13,23,24,34}
{12,13,14,23,24}
{12,13,14,24,34}
{12,13,23,24,34}
{13,14,23,24,34}
{12,13,14,23,24,34}


MATHEMATICA

Table[Length[Select[Subsets[Subsets[Range[n], {2}]], !OrderedQ[Last/@#]&]], {n, 0, 5}]


PROG

(PARI) seq(n)={my(p=1 + 3/2*x  x^2  x/2*sqrt(1  12*x + 4*x^2 + O(x^n))); concat([0], vector(n, k, 2^binomial(k, 2)polcoef(p, k)))} \\ Andrew Howroyd, Aug 26 2019


CROSSREFS

Nesting (or crossing) set partitions are A016098.
MMnumbers of nesting multiset partitions are A326256.


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



