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

A350415 Number of acyclic digraphs on n unlabeled nodes with a global source (or sink).

Original entry on oeis.org

1, 1, 3, 16, 164, 3341, 138101, 11578037, 1961162564, 668678055847, 457751797355605, 628137837068751147, 1726130748679532455689, 9493834992383031007906911, 104476428350838383854529661007, 2299979227717819421763629684068904

Offset: 1

Andrew Howroyd, Dec 29 2021

nonn

A local source (also called an out-node) is a node whose in-degree is zero. In the case of an acyclic digraph with only one local source, the source is also a global source.

Andrew Howroyd, Table of n, a(n) for n = 1..50
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

The labeled case is A003025.
Row sums of A350488.
A diagonal of A122078.
Cf. A003087, A345258, A350360.

A350415seq(16) \\ See PARI link in A122078 for program code.

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

A058876 Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n).

Original entry on oeis.org

1, 1, 2, 1, 9, 15, 1, 28, 198, 316, 1, 75, 1610, 10710, 16885, 1, 186, 10575, 211820, 1384335, 2174586, 1, 441, 61845, 3268125, 64144675, 416990763, 654313415, 1, 1016, 336924, 43832264, 2266772550, 44218682312, 286992935964, 450179768312

Offset: 1

N. J. A. Sloane, Jan 07 2001

			Triangle begins:
  1;
  1,  2;
  1,  9,   15;
  1, 28,  198,   316;
  1, 75, 1610, 10710, 16885;
  ...

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
R. W. Robinson, Counting labeled acyclic digraphs, pp. 239-273 of F. Harary, editor, New Directions in the Theory of Graphs. Academic Press, NY, 1973.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)

Columns give A058877, A060337.
Diagonals give A003025, A003026, A060335.
Row sums give A003024.
Cf. A122078 (unlabeled case).

a[p_, k_] :=a[p, k] =If[p == k, 1, Sum[Binomial[p, k]*a[p - k, n]*(2^k - 1)^n*2^(k (p - k - n)), {n,1, p - k}]];
Map[Reverse, Table[Table[a[p, k], {k, 1, p}], {p, 1, 6}]] // Grid (* Geoffrey Critzer, Aug 29 2016 *)

A058876(n)={my(v=vector(n)); for(n=1, #v, v[n]=vector(n, i, if(i==n, 1, my(u=v[n-i]); sum(j=1, #u, 2^(i*(#u-j))*(2^i-1)^j*binomial(n,i)*u[j])))); v}
{ my(T=A058876(10)); for(n=1, #T, print(Vecrev(T[n]))) } \\ Andrew Howroyd, Dec 27 2021

Harary and Prins (following Robinson) give a recurrence.

More terms from Vladeta Jovovic, Apr 10 2001

A345258 Number of acyclic digraphs (or DAGs) on n unlabeled vertices with one source and one sink.

Original entry on oeis.org

1, 1, 2, 10, 98, 1960, 80176, 6686760, 1129588960, 384610774696, 263104175114712, 360908867732030980, 991603865814038728388, 5453395569997436383751204, 60010050181461052836515513108, 1321051495313052133670927704328040, 58170762510305449187073353930875222256

Offset: 1

Max Alekseyev, Jun 12 2021

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50 (terms 1..40 from Mikhail Tikhomirov)
Marcel et al., Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?, MathOverflow, 2021.

Row sums of A350491.
The labeled version is A165950.
Cf. A003087, A049531, A122078, A350415, A350492.

A345258seq(16) \\ See PARI link in A122078 for program code.

a(9) from Brendan McKay.

Terms a(10) and beyond from Mikhail Tikhomirov, Jun 16 2021

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

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

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 4, 9, 9, 6, 1, 1, 1, 4, 12, 37, 60, 80, 63, 33, 10, 1, 1, 1, 4, 13, 51, 163, 407, 796, 1169, 1291, 1057, 649, 281, 85, 15, 1, 1, 1, 4, 13, 54, 215, 846, 2690, 7253, 15703, 27596, 39057, 44902, 41723, 31336, 18844, 8983, 3325, 920, 180, 21, 1

Offset: 0

Andrew Howroyd, Dec 31 2021

			Triangle begins:
  [0] 1;
  [1] 1;
  [2] 1, 1;
  [3] 1, 1, 3,  1;
  [4] 1, 1, 4,  9,  9,  6,  1;
  [5] 1, 1, 4, 12, 37, 60, 80, 63, 33, 10, 1;
  ...

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

The labeled version is A081064.
Row sums are A003087.
Cf. A122078, A350449.

\\ See PARI link in A122078 for program code.
{ my(T=AcyclicDigraphsByArcs(6)); 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])) }

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

A350415 Number of acyclic digraphs on n unlabeled nodes with a global source (or sink).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

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

A058876 Triangle read by rows: T(n,k) = number of labeled acyclic digraphs with n nodes, containing exactly n+1-k points of in-degree zero (n >= 1, 1<=k<=n).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A345258 Number of acyclic digraphs (or DAGs) on n unlabeled vertices with one source and one sink.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Extensions

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

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

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

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