A326237 Number of non-nesting digraphs with vertices {1..n}, where two edges (a,b), (c,d) are nesting if a < c and b > d or a > c and b < d.

1, 2, 12, 104, 1008, 10272, 107712, 1150592

Offset: 0

Author

Gus Wiseman, Jun 19 2019

Keywords

• nonn
• more

Comments

These are digraphs with the property that, if the edges are listed in lexicographic order, the sequence of targets is weakly increasing. For example, the digraph with lexicographically ordered edge set {(1,2),(2,1),(3,1),(3,2)} is nesting because the targets are (2,1,1,2), a sequence that is not weakly increasing.

Also the number of non-semicrossing digraphs with vertices {1..n}, where two edges (a,b), (c,d) are semicrossing if a < c and b < d or a > c and b > d. For example, the a(2) = 4 non-semicrossing digraph edge-sets are:

{}

{11}

{12}

{21}

{22}

{11,12}

{11,21}

{12,21}

{12,22}

{21,22}

{11,12,21}

{12,21,22}

Apparently a duplicate of A152254. - R. J. Mathar, Jul 12 2019

Examples

			The a(2) = 12 non-nesting digraph edge-sets:
  {}
  {11}
  {12}
  {21}
  {22}
  {11,12}
  {11,21}
  {11,22}
  {12,22}
  {21,22}
  {11,12,22}
  {11,21,22}
		

Crossrefs

Nesting digraphs are A326209.

Non-nesting set partitions are A000108.

Non-capturing set partitions are A054391.

Cf. A002416, A002720, A054391, A058681, A122880, A229865.

Cf. A326249, A326250, A326251, A326256, A326257.

Programs

Mathematica

Table[Length[Select[Subsets[Tuples[Range[n],2]],OrderedQ[Last/@#]&]],{n,4}]

Formula

A002416(n) = a(n) + A326209(n).