A326294 Number of connected simple graphs on a subset of {1..n} with no crossing or nesting edges.

1, 1, 2, 8, 35, 147, 600, 2418

Offset: 0

Author

Gus Wiseman, Jun 29 2019

Keywords

• nonn
• more

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.

Examples

			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}
		

Links

• Eric Marberg, Crossings and nestings in colored set partitions, arXiv preprint arXiv:1203.5738 [math.CO], 2012.

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.

Cf. A006125, A054726, A117662, A136653.

Cf. A324169, A326210, A326293, A326340.

Programs

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
				

Formula

Conjecture: a(n) = A052161(n - 2) + 1.