A101228 -id:A101228 - cp's OEIS frontend

A003087 Number of acyclic digraphs with n unlabeled nodes.

1, 1, 2, 6, 31, 302, 5984, 243668, 20286025, 3424938010, 1165948612902, 797561675349580, 1094026876269892596, 3005847365735456265830, 16530851611091131512031070, 181908117707763484218885361402

Offset: 0

N. J. A. Sloane

Also the number of equivalence classes of n X n real (0,1)-matrices with all eigenvalues positive, up to conjugation by permutations.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 194.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 0..50 (terms 0..18 were computed by R. W. Robinson; terms 19..36 by Sean A. Irvine, Jan 22 2014)
Jack Kuipers and Giusi Moffa, Uniform generation of random acyclic digraphs, arXiv preprint arXiv:1202.6590 [stat.CO], 2012. - _N. J. A. Sloane_, Sep 14 2012
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, J. Integer Sequences, 7 (2004), #04.3.3.
B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, Acyclic digraphs and eigenvalues of (0,1)-matrices, arXiv:math/0310423 [math.CO], 2003.
Lawrence Ong, Optimal Finite-Length and Asymptotic Index Codes for Five or Fewer Receivers, arXiv preprint arXiv:1606.05982 [cs.IT], 2016.
R. W. Robinson, Counting unlabeled acyclic digraphs, in Little C.H.C. (Ed.), "Combinatorial Mathematics V (Melbourne 1976)", Lect. Notes Math. 622 (1976), pp. 28-43. DOI:10.1007/BFb0069178.
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)
Eric Weisstein's World of Mathematics, Acyclic Digraph.
Index entries for sequences related to binary matrices

Cf. A003024 (the labeled case), A082402, A101228 (weakly connected, inverse Euler Trans).

Rows sums of A122078, A350447, A350448.

A350449 Triangle read by rows: T(n,k) is the number of weakly connected acyclic digraphs on n unlabeled nodes with k arcs, n >= 1, k = 0..(n-1)*n/2.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 1, 0, 0, 0, 8, 9, 6, 1, 0, 0, 0, 0, 27, 54, 79, 63, 33, 10, 1, 0, 0, 0, 0, 0, 91, 320, 732, 1136, 1281, 1056, 649, 281, 85, 15, 1, 0, 0, 0, 0, 0, 0, 350, 1788, 6012, 14378, 26529, 38407, 44621, 41638, 31321, 18843, 8983, 3325, 920, 180, 21, 1

Offset: 1

Andrew Howroyd, Dec 31 2021

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 3, 1;
  [4] 0, 0, 0, 8,  9,  6,  1;
  [5] 0, 0, 0, 0, 27, 54, 79, 63, 33, 10, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1350 (rows 1..20)

Row sums are A101228.
Columns sums are A350451.
Leading diagonal is A000238.
Cf. A350447 (not necessarily connected), A350450 (transpose).

\\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsByArcs(6)); for(n=1, #T, print(T[n])) }

A350450 Triangle read by rows: T(n,k) is the number of unlabeled weakly connected acyclic digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.

Original entry on oeis.org

1, 0, 1, 0, 0, 3, 0, 0, 1, 8, 0, 0, 0, 9, 27, 0, 0, 0, 6, 54, 91, 0, 0, 0, 1, 79, 320, 350, 0, 0, 0, 0, 63, 732, 1788, 1376, 0, 0, 0, 0, 33, 1136, 6012, 9933, 5743, 0, 0, 0, 0, 10, 1281, 14378, 45225, 54502, 24635, 0, 0, 0, 0, 1, 1056, 26529, 151848, 322736, 298250, 108968

Offset: 0

Andrew Howroyd, Dec 31 2021

			Triangle begins:
  1;
  0, 1;
  0, 0, 3;
  0, 0, 1, 8;
  0, 0, 0, 9, 27;
  0, 0, 0, 6, 54,   91;
  0, 0, 0, 1, 79,  320,  350;
  0, 0, 0, 0, 63,  732, 1788, 1376;
  0, 0, 0, 0, 33, 1136, 6012, 9933, 5743;
  ...

Andrew Howroyd, Table of n, a(n) for n = 0..860 (rows 0..40)

Main diagonal is A000238.
Row sums are A350451.
Column sums are A101228.
Cf. A122078, A350449 (transpose).

\\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsTr(10)); for(n=1, #T, print(T[n])); }

A350451 Number of weakly connected acyclic digraphs with n arcs.

Original entry on oeis.org

1, 1, 3, 9, 36, 151, 750, 3959, 22857, 140031, 909388, 6202031, 44256875, 328994157, 2540242646, 20317980102, 167980915848, 1432808198569, 12587788263807, 113739153822878, 1055610955120803, 10051265993496814, 98083750658261085, 979961276867802001, 10015362142357613001

Offset: 0

Andrew Howroyd, Dec 31 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 0..40

Row sums of A350450.
Column sums of A350449.
Cf. A101228, A122078.

\\ See PARI link in A122078 for program code.
{ my(T=WeakAcyclicDigraphsTr(15)); vector(#T, n, vecsum(T[n])) }

A361587 Triangle read by rows: T(n,k) is the number of weakly connected digraphs on n unlabeled nodes with k strongly connected components.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 5, 4, 4, 0, 83, 56, 36, 24, 0, 5048, 2406, 1101, 542, 267, 0, 1047008, 324917, 101307, 37017, 14947, 5647, 0, 705422362, 136882286, 27757789, 7134897, 2257234, 779257, 237317, 0, 1580348371788, 183851281949, 23086772643, 3922864504, 907027520, 258909828, 78691767, 20035307

Offset: 0

Andrew Howroyd, Mar 16 2023

			Triangle begins:
  1;
  0,       1;
  0,       1,      1;
  0,       5,      4,      4;
  0,      83,     56,     36,    24;
  0,    5048,   2406,   1101,   542,   267;
  0, 1047008, 324917, 101307, 37017, 14947, 5647;
  ...

Column k=1 is A035512.
Main diagonal is A101228.
Row sums are A003085.
Cf. A350794, A361582, A361588.

\\ See PARI link in A350794 for program code.
{ my(A=A361587triang(6)); for(n=1, #A, print(A[n])) }

cp's OEIS Frontend

A003087 Number of acyclic digraphs with n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A350449 Triangle read by rows: T(n,k) is the number of weakly connected acyclic digraphs on n unlabeled nodes with k arcs, n >= 1, k = 0..(n-1)*n/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350450 Triangle read by rows: T(n,k) is the number of unlabeled weakly connected acyclic digraphs with n arcs and k vertices, n >= 0, k = 1..n+1.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350451 Number of weakly connected acyclic digraphs with n arcs.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

A361587 Triangle read by rows: T(n,k) is the number of weakly connected digraphs on n unlabeled nodes with k strongly connected components.

Views

Author

Keywords

Examples

Crossrefs

Programs

PARI