A326251 -id:A326251 - 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.

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

Offset: 0

Gus Wiseman, Jun 19 2019

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

			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}

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.

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

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

A229865 Number of n X n 0..1 arrays with corresponding row and column sums equal.

Original entry on oeis.org

1, 2, 8, 80, 2432, 247552, 88060928, 112371410944, 523858015518720, 9041009511609073664, 583447777113052431515648, 141885584718620229407228821504, 130832005909904417592540055577034752, 459749137931232137234615429529864283095040, 6182706200522446492946534924719926752508110700544

Offset: 0

R. H. Hardin, Oct 01 2013

nonn

Also known as labeled Eulerian digraphs allowing loops. - Brendan McKay, May 12 2019

			Some solutions for n=4:
  0 0 0 1     0 0 1 0     0 0 0 1     0 0 1 0     0 0 1 1
  0 1 0 0     1 0 0 0     1 0 1 0     0 0 1 1     1 0 0 1
  0 0 0 1     0 1 0 0     0 1 0 1     0 1 1 1     1 1 1 0
  1 0 1 0     0 0 0 1     0 1 1 0     1 1 0 0     0 1 1 1
From _Gus Wiseman_, Jun 22 2019: (Start)
The a(3) = 8 Eulerian digraph edge-sets:
  {}
  {11}
  {22}
  {11,22}
  {12,21}
  {11,12,21}
  {12,21,22}
  {11,12,21,22}
(End)

Mohammad Behzad Kang and Andrew Salch, The mod p cohomology of the Morava stabilizer group at large primes, arXiv:2410.24171 [math.AT], 2024. See p. 46.

Column 1 of A229870.
The unlabeled version is A308111.
Cf. A000595, A002416, A002720, A007080.
Cf. A326209, A326237, A326251, A326252, A326253.

Table[Length[Select[Subsets[Tuples[Range[n],2]],Sort[First/@#]==Sort[Last/@#]&]],{n,4}] (* Gus Wiseman, Jun 22 2019 *)

a(n) = 2^n * A007080(n). - Andrew Howroyd, Sep 11 2019

a(0)=1 prepended by Alois P. Heinz, May 14 2019

Terms a(11) and beyond from Andrew Howroyd, Sep 11 2019

A326252 Number of digraphs with vertices {1..n} whose increasing edges are crossing.

Original entry on oeis.org

0, 0, 0, 0, 16384, 22020096, 62679678976, 556181084962816

Offset: 0

Gus Wiseman, Jun 30 2019

A directed edge (a,b) is increasing if a < b. Two edges (a,b), (c,d) are crossing if a < c < b < d or c < a < d < b.

Simple graphs whose edges are crossing are A326210.
Digraphs whose increasing edges are not crossing are A326251.
Digraphs whose edges are not crossing are A326237.
Cf. A002416, A002720, A229865, A324170, A326209, A326252, A326258.

croXQ[eds_]:=MatchQ[eds,{_,{x_,y_},_,{z_,t_},_}/;x

a(n) = 2^(n * (n + 1)/2) * A326210(n).

A326253 Number of sequences of distinct ordered pairs of positive integers up to n.

Original entry on oeis.org

1, 2, 65, 986410, 56874039553217, 42163840398198058854693626, 1011182700521015817607065606491025592595137, 1653481537585545171449931620186035466059689728986775126016505970

Offset: 0

Gus Wiseman, Jun 21 2019

nonn

			The a(2) = 65 sequences:
  ()  (11)  (11,12)  (11,12,21)  (11,12,21,22)
      (12)  (11,21)  (11,12,22)  (11,12,22,21)
      (21)  (11,22)  (11,21,12)  (11,21,12,22)
      (22)  (12,11)  (11,21,22)  (11,21,22,12)
            (12,21)  (11,22,12)  (11,22,12,21)
            (12,22)  (11,22,21)  (11,22,21,12)
            (21,11)  (12,11,21)  (12,11,21,22)
            (21,12)  (12,11,22)  (12,11,22,21)
            (21,22)  (12,21,11)  (12,21,11,22)
            (22,11)  (12,21,22)  (12,21,22,11)
            (22,12)  (12,22,11)  (12,22,11,21)
            (22,21)  (12,22,21)  (12,22,21,11)
                     (21,11,12)  (21,11,12,22)
                     (21,11,22)  (21,11,22,12)
                     (21,12,11)  (21,12,11,22)
                     (21,12,22)  (21,12,22,11)
                     (21,22,11)  (21,22,11,12)
                     (21,22,12)  (21,22,12,11)
                     (22,11,12)  (22,11,12,21)
                     (22,11,21)  (22,11,21,12)
                     (22,12,11)  (22,12,11,21)
                     (22,12,21)  (22,12,21,11)
                     (22,21,11)  (22,21,11,12)
                     (22,21,12)  (22,21,12,11)

Cf. A000522, A000595, A002416, A095661, A229865, A326209, A326237, A326251, A326252, A326258.

Table[Sum[k!*Binomial[n^2,k],{k,0,n^2}],{n,0,4}]

a(n) = A000522(n^2).

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A229865 Number of n X n 0..1 arrays with corresponding row and column sums equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A326252 Number of digraphs with vertices {1..n} whose increasing edges are crossing.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A326253 Number of sequences of distinct ordered pairs of positive integers up to n.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula