A326209 Number of nesting labeled digraphs with vertices {1..n}.

0, 0, 4, 408, 64528

Offset: 0

Author

Gus Wiseman, Jun 19 2019

Keywords

• nonn
• more

Comments

Two edges (a,b), (c,d) are nesting if a < c and b > d or a > c and b < d.

Also unsortable digraphs with vertices {1..n}, where a digraph is sortable if, when the edges are listed in lexicographic order, their targets are weakly increasing.

Also the number of 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 semicrossing digraph edge-sets are:

{11,22}

{11,12,22}

{11,21,22}

{11,12,21,22}

Examples

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

Crossrefs

Non-nesting digraphs are A326237.

Nesting set partitions are A016098.

MM-numbers of nesting multiset partitions are A326256.

MM-numbers of unsortable multiset partitions are A326258.

Cf. A000108, A001519, A002416, A229865.

Cf. A326210, A326211, A326243, A326246, A326248, A326250.

Programs

Mathematica

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

Formula

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