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,2

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

Links

Table of n, a(n) for n=0..7.

Formula

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

Example

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}

Mathematica

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

Crossrefs

Nesting digraphs are A326209.

Non-nesting set partitions are A000108.

Non-capturing set partitions are A326254.

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

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

Sequence in context: A302357 A052693 A050621 * A152254 A157328 A061632

Adjacent sequences: A326234 A326235 A326236 * A326238 A326239 A326240

Keyword

nonn,more

Author

Gus Wiseman, Jun 19 2019

Status

approved