login
A326294
Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.
3
1, 1, 2, 8, 35, 147, 600, 2418
OFFSET
0,3
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
Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.
FORMULA
Conjecture: a(n) = A052161(n - 2) + 1.
EXAMPLE
The a(4) = 35 edge-sets:
{} {12} {12,13} {12,13,14} {12,13,14,34}
{13} {12,14} {12,13,23} {12,13,23,34}
{14} {12,23} {12,13,34} {12,14,24,34}
{23} {12,24} {12,14,24} {12,23,24,34}
{24} {13,14} {12,14,34}
{34} {13,23} {12,23,24}
{13,34} {12,23,34}
{14,24} {12,24,34}
{14,34} {13,14,34}
{23,24} {13,23,34}
{23,34} {14,24,34}
{24,34} {23,24,34}
MATHEMATICA
csm[s_]:=With[{c=Select[Tuples[Range[Length[s]], 2], And[OrderedQ[#], UnsameQ@@#, Length[Intersection@@s[[#]]]>0]&]}, If[c=={}, s, csm[Sort[Append[Delete[s, List/@c[[1]]], Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n], {2}]], Length[csm[#]]<=1&&!MatchQ[#, {___, {x_, y_}, ___, {z_, t_}, ___}/; x<z<y<t||z<x<t<y||x<z<t<y||z<x<y<t]&]], {n, 0, 5}]
CROSSREFS
The inverse binomial transform is the covering case A326339.
Covering graphs with no crossing or nesting edges are A326329.
Connected simple graphs are A001349.
Graphs without crossing or nesting edges are A326244.
Sequence in context: A116618 A037723 A037618 * A184786 A082759 A243204
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Jun 29 2019
STATUS
approved