|
|
A326294
|
|
Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.
|
|
3
|
|
|
|
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
|
|
|
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.
|
|
KEYWORD
|
nonn,more
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|