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

A122078 Triangle read by rows: T(n,k) is the number of unlabeled acyclic digraphs with n >= 0 nodes and n-k outnodes (0 <= k <= n).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 3, 0, 1, 3, 11, 16, 0, 1, 4, 25, 108, 164, 0, 1, 5, 47, 422, 2168, 3341, 0, 1, 6, 78, 1251, 15484, 88747, 138101, 0, 1, 7, 120, 3124, 79836, 1215783, 7409117, 11578037, 0, 1, 8, 174, 6925, 333004, 11620961, 199203464, 1252610909, 1961162564, 0

Offset: 0

N. J. A. Sloane, Oct 18 2006

			Triangle T(n,k) begins:
  1:
  1, 0;
  1, 1,  0;
  1, 2,  3,    0;
  1, 3, 11,   16,     0;
  1, 4, 25,  108,   164,     0;
  1, 5, 47,  422,  2168,  3341,      0;
  1, 6, 78, 1251, 15484, 88747, 138101, 0;
  ...

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

Andrew Howroyd, Table of n, a(n) for n = 0..495 (rows 0..30; rows 0..15 from R. W. Robinson)
Andrew Howroyd, PARI program, Dec 2021, updated Jan 2022.

Row sums give A003087.
Diagonals include A000007, A350415.
Cf. A058876 (labeled case), A350447, A350448, A350449, A350450.

\\ See link for program code.
{ my(T=AcyclicDigraphsByNonSources(8)); for(n=1, #T, print(T[n])) } \\ Andrew Howroyd, Dec 31 2021

Zero terms inserted by Andrew Howroyd, Dec 29 2021

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])) }

A350488 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs and a global source, n >= 1, k = 0..n*(n-1)/2.

Original entry on oeis.org

1, 0, 1, 0, 0, 2, 1, 0, 0, 0, 4, 6, 5, 1, 0, 0, 0, 0, 9, 25, 47, 46, 27, 9, 1, 0, 0, 0, 0, 0, 20, 95, 297, 582, 783, 738, 501, 235, 75, 14, 1, 0, 0, 0, 0, 0, 0, 48, 337, 1575, 4941, 11295, 19404, 25847, 26966, 22195, 14380, 7280, 2831, 816, 165, 20, 1

Offset: 1

Andrew Howroyd, Jan 01 2022

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 2, 1;
  [4] 0, 0, 0, 4, 6,  5,  1;
  [5] 0, 0, 0, 0, 9, 25, 47, 46, 27, 9, 1;
  [6] 0, 0, 0, 0, 0, 20, 95, 297, 582, 783, 738, 501, 235, 75, 14, 1;
  ...

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

Row sums are A350415.
Column sums are A350490.
Leading diagonal is A000081.
The labeled version is A350487.
Cf. A122078, A350447, A350449, A350491.

\\ See PARI link in A122078 for program code.
{ my(A=A350488rows(7)); for(i=1, #A, print(A[i])) }

A350491 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs and a global source and sink, n >= 1, k = 0..n*(n-1)/2.

Original entry on oeis.org

1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 4, 4, 1, 0, 0, 0, 0, 1, 9, 25, 32, 22, 8, 1, 0, 0, 0, 0, 0, 1, 17, 92, 259, 441, 496, 379, 195, 66, 13, 1, 0, 0, 0, 0, 0, 0, 1, 28, 259, 1286, 4026, 8754, 13930, 16686, 15289, 10785, 5842, 2397, 722, 151, 19, 1

Offset: 1

Andrew Howroyd, Jan 08 2022

			Triangle begins:
  [1] 1;
  [2] 0, 1;
  [3] 0, 0, 1, 1;
  [4] 0, 0, 0, 1, 4, 4,  1;
  [5] 0, 0, 0, 0, 1, 9, 25, 32,  22,   8,   1;
  [6] 0, 0, 0, 0, 0, 1, 17, 92, 259, 441, 496, 379, 195, 66, 13, 1;
  ...

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

Row sums are A345258.
Column sums are A350492.
Cf. A122078, A350447, A350449, A350488.

\\ See PARI link in A122078 for program code.
{ my(A=A350491rows(7)); for(i=1, #A, print(A[i])) }

cp's OEIS Frontend

A003087 Number of acyclic digraphs with n unlabeled nodes.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A122078 Triangle read by rows: T(n,k) is the number of unlabeled acyclic digraphs with n >= 0 nodes and n-k outnodes (0 <= k <= n).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

PARI

Extensions

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

A350488 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs and a global source, n >= 1, k = 0..n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A350491 Triangle read by rows: T(n,k) is the number of acyclic digraphs on n unlabeled nodes with k arcs and a global source and sink, n >= 1, k = 0..n*(n-1)/2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI