login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)