cp's OEIS Frontend

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.

%I A326237 #20 Oct 29 2024 19:53:35
%S A326237 1,2,12,104,1008,10272,107712,1150592
%N 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.
%C A326237 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.
%C A326237 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:
%C A326237   {}
%C A326237   {11}
%C A326237   {12}
%C A326237   {21}
%C A326237   {22}
%C A326237   {11,12}
%C A326237   {11,21}
%C A326237   {12,21}
%C A326237   {12,22}
%C A326237   {21,22}
%C A326237   {11,12,21}
%C A326237   {12,21,22}
%C A326237 Apparently a duplicate of A152254. - _R. J. Mathar_, Jul 12 2019
%F A326237 A002416(n) = a(n) + A326209(n).
%e A326237 The a(2) = 12 non-nesting digraph edge-sets:
%e A326237   {}
%e A326237   {11}
%e A326237   {12}
%e A326237   {21}
%e A326237   {22}
%e A326237   {11,12}
%e A326237   {11,21}
%e A326237   {11,22}
%e A326237   {12,22}
%e A326237   {21,22}
%e A326237   {11,12,22}
%e A326237   {11,21,22}
%t A326237 Table[Length[Select[Subsets[Tuples[Range[n],2]],OrderedQ[Last/@#]&]],{n,4}]
%Y A326237 Nesting digraphs are A326209.
%Y A326237 Non-nesting set partitions are A000108.
%Y A326237 Non-capturing set partitions are A054391.
%Y A326237 Cf. A002416, A002720, A054391, A058681, A122880, A229865.
%Y A326237 Cf. A326249, A326250, A326251, A326256, A326257.
%K A326237 nonn,more
%O A326237 0,2
%A A326237 _Gus Wiseman_, Jun 19 2019