A122078 -id:A122078

A003087

Number of acyclic digraphs with n unlabeled nodes.
(Formerly M1696)

+0
24

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

COMMENTS

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

REFERENCES

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).

LINKS

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

CROSSREFS

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

Rows sums of A122078, A350447, A350448.

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

STATUS

approved

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).

+0
8

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,3

REFERENCES

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.

LINKS

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)

FORMULA

Harary and Prins (following Robinson) give a recurrence.

EXAMPLE

Triangle begins:

1;

1, 2;

1, 9, 15;

1, 28, 198, 316;

1, 75, 1610, 10710, 16885;

...

MATHEMATICA

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 *)

PROG

(PARI)

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

CROSSREFS

Columns give A058877, A060337.

Diagonals give A003025, A003026, A060335.

Row sums give A003024.

Cf. A122078 (unlabeled case).

KEYWORD

nonn,easy,tabl

AUTHOR

N. J. A. Sloane, Jan 07 2001

EXTENSIONS

More terms from Vladeta Jovovic, Apr 10 2001

STATUS

approved

A345258

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

+0
8

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

LINKS

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.

PROG

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

CROSSREFS

Row sums of A350491.

The labeled version is A165950.

Cf. A003087, A049531, A122078, A350415, A350492.

KEYWORD

nonn

AUTHOR

Max Alekseyev, Jun 12 2021

EXTENSIONS

a(9) from Brendan McKay.

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

STATUS

approved

A350415

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

+0
10

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,3

COMMENTS

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.

LINKS

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.

PROG

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

CROSSREFS

The labeled case is A003025.

Row sums of A350488.

A diagonal of A122078.

Cf. A003087, A345258, A350360.

KEYWORD

nonn

AUTHOR

Andrew Howroyd, Dec 29 2021

STATUS

approved

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.

+0
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,7

LINKS

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

EXAMPLE

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;

...

PROG

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

{ my(T=AcyclicDigraphsByArcs(6)); for(n=1, #T, print(T[n])) }

CROSSREFS

The labeled version is A081064.

Row sums are A003087.

Cf. A122078, A350449.

KEYWORD

nonn,tabf

AUTHOR

Andrew Howroyd, Dec 31 2021

STATUS

approved

A350448

Triangle read by rows: T(n,k) is the number of acyclic graphs on n unlabeled nodes whose longest directed path has k arcs.

+0
2

1, 1, 0, 1, 1, 0, 1, 3, 2, 0, 1, 8, 14, 8, 0, 1, 20, 89, 128, 64, 0, 1, 55, 634, 1934, 2336, 1024, 0, 1, 163, 5668, 36428, 83648, 84992, 32768, 0, 1, 556, 67926, 959718, 3919584, 7097088, 6144000, 2097152, 0, 1, 2222, 1137641, 37205922, 268989920, 793138688, 1175224320, 880803840, 268435456, 0

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,8

LINKS

Table of n, a(n) for n=0..54.

EXAMPLE

Triangle begins:

1;

1, 0;

1, 1, 0;

1, 3, 2, 0;

1, 8, 14, 8, 0;

1, 20, 89, 128, 64, 0;

1, 55, 634, 1934, 2336, 1024, 0;

1, 163, 5668, 36428, 83648, 84992, 32768, 0;

...

PROG

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

{ my(T=AcyclicDigraphsByLongestPath(8)); for(n=1, #T, print(T[n])) }

CROSSREFS

Row sums are A003087.

Diagonals include A000007, A006125.

Cf. A122078.

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Dec 31 2021

STATUS

approved

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.

+0
9

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

LINKS

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

EXAMPLE

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;

...

PROG

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

{ my(T=WeakAcyclicDigraphsByArcs(6)); for(n=1, #T, print(T[n])) }

CROSSREFS

Row sums are A101228.

Columns sums are A350451.

Leading diagonal is A000238.

Cf. A350447 (not necessarily connected), A350450 (transpose).

KEYWORD

nonn,tabf

AUTHOR

Andrew Howroyd, Dec 31 2021

STATUS

approved

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.

+0
7

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,6

LINKS

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

EXAMPLE

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;

...

PROG

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

{ my(T=WeakAcyclicDigraphsTr(10)); for(n=1, #T, print(T[n])); }

CROSSREFS

Main diagonal is A000238.

Row sums are A350451.

Column sums are A101228.

Cf. A122078, A350449 (transpose).

KEYWORD

nonn,tabl

AUTHOR

Andrew Howroyd, Dec 31 2021

STATUS

approved

A350451

Number of weakly connected acyclic digraphs with n arcs.

+0
6

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,3

LINKS

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

PROG

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

{ my(T=WeakAcyclicDigraphsTr(15)); vector(#T, n, vecsum(T[n])) }

CROSSREFS

Row sums of A350450.

Column sums of A350449.

Cf. A101228, A122078.

KEYWORD

nonn

AUTHOR

Andrew Howroyd, Dec 31 2021

STATUS

approved

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.

+0
5

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,6

LINKS

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

EXAMPLE

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;

...

PROG

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

{ my(A=A350488rows(7)); for(i=1, #A, print(A[i])) }

CROSSREFS

Row sums are A350415.

Column sums are A350490.

Leading diagonal is A000081.

The labeled version is A350487.

Cf. A122078, A350447, A350449, A350491.

KEYWORD

nonn,tabf

AUTHOR

Andrew Howroyd, Jan 01 2022

STATUS

approved