The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003024 Number of acyclic digraphs (or DAGs) with n labeled nodes.
(Formerly M3113)

%I M3113

%S 1,1,3,25,543,29281,3781503,1138779265,783702329343,1213442454842881,

%T 4175098976430598143,31603459396418917607425,

%U 521939651343829405020504063,18676600744432035186664816926721,1439428141044398334941790719839535103

%N Number of acyclic digraphs (or DAGs) with n labeled nodes.

%C Also the number of n X n real (0,1)-matrices with all eigenvalues positive. - Conjectured by _Eric W. Weisstein_, Jul 10 2003 and proved by McKay et al. 2003, 2004

%C Also the number of n X n real (0,1)-matrices with permanent equal to 1, up to permutation of rows/columns, cf. A089482. - _Vladeta Jovovic_, Oct 28 2009

%C Also the number of nilpotent elements in the semigroup of binary relations on [n]. - _Geoffrey Critzer_, May 26 2022

%D Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.

%D S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 310.

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).

%D 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.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%D R. P Stanley, Enumerative Combinatorics I, 2nd. ed., p. 322.

%H T. D. Noe, <a href="/A003024/b003024.txt">Table of n, a(n) for n = 0..40</a>

%H T. E. Allen, J. Goldsmith, and N. Mattei, <a href="http://cs.engr.uky.edu/~goldsmit/papers/gen-cpnets.pdf">Counting, Ranking, and Randomly Generating CP-nets</a>, 2014.

%H Huantian Cao, <a href="http://cobweb.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002.

%H Huantian Cao, <a href="/A000009/a000009.pdf">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002 [Local copy, with permission]

%H Eunice Y.-J. Chen, A. Choi, and A. Darwiche, <a href="http://proceedings.mlr.press/v52/chen16.pdf">On Pruning with the MDL Score</a>, JMLR: Workshop and Conference Proceedings vol 52, 98-109, 2016.

%H S. Engstrom, <a href="http://www.sci.kth.se/polopoly_fs/1.364961!/Menu/general/column-content/attachment/final_3_Random%20orientations.pdf">Random acyclic orientations of graphs</a>, Master's thesis written at the department of Mathematics at the Royal Institute of Technology (KTH) in Stockholm, Jan. 2013.

%H Jack Kuipers and Giusi Moffa, <a href="http://arxiv.org/abs/1202.6590">Uniform generation of random acyclic digraphs</a>, arXiv preprint arXiv:1202.6590 [stat.CO], 2012. - _N. J. A. Sloane_, Sep 14 2012

%H Laphou Lao, Zecheng Li, Songlin Hou, Bin Xiao, Songtao Guo, and Yuanyuan Yang, <a href="https://doi.org/10.1145/3372136">A Survey of IoT Applications in Blockchain Systems: Architecture, Consensus and Traffic Modeling</a>, ACM Computing Surveys (CSUR, 2020) Vol. 53, No. 1, Article No. 18.

%H B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html">Acyclic digraphs and eigenvalues of (0,1)-matrices</a>, J. Integer Sequences, 7 (2004), #04.3.3.

%H B. D. McKay, F. E. Oggier, G. F. Royle, N. J. A. Sloane, I. M. Wanless and H. S. Wilf, <a href="http://arXiv.org/abs/math.CO/0310423">Acyclic digraphs and eigenvalues of (0,1)-matrices</a>, arXiv:math/0310423 [math.CO], Oct 28 2003.

%H A. Motzek and R. Möller, <a href="https://www.ifis.uni-luebeck.de/uploads/tx_wapublications/ai-dbn-motzek-public-ga.pdf">Exploiting Innocuousness in Bayesian Networks</a>, Preprint 2015.

%H Yisu Peng, Y. Jiang, and P. Radivojac, <a href="https://arxiv.org/abs/1712.09679">Enumerating consistent subgraphs of directed acyclic graphs: an insight into biomedical ontologies</a>, arXiv preprint arXiv:1712.09679 [cs.DS], 2017.

%H J. Peters, J. Mooij, D. Janzing, and B. Schölkopf, <a href="http://arxiv.org/abs/1309.6779">Causal Discovery with Continuous Additive Noise Models</a>, arXiv preprint arXiv:1309.6779 [stat.ML], 2013.

%H R. W. Robinson, <a href="/A003024/a003024.pdf">Enumeration of acyclic digraphs</a>, Manuscript. (Annotated scanned copy)

%H V. I. Rodionov, <a href="https://doi.org/10.1016/0012-365X(92)90155-9">On the number of labeled acyclic digraphs</a>, Disc. Math. 105 (1-3) (1992) 319-321

%H I. Shpitser, T. S. Richardson, J. M. Robins and R. Evans, <a href="http://arxiv.org/abs/1207.5058">Parameter and Structure Learning in Nested Markov Models</a>, arXiv preprint arXiv:1207.5058 [stat.ML], 2012.

%H I. Shpitser, R. J. Evans, T. S. Richardson, and J. M. Robins, <a href="https://doi.org/10.2333/bhmk.41.3">Introduction to nested Markov models</a>, Behaviormetrika, Behaviormetrika Vol. 41, No. 1, 2014, 3-39.

%H R. P. Stanley, <a href="http://www-math.mit.edu/~rstan/pubs/pubfiles/18.pdf">Acyclic orientation of graphs,</a> Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.

%H S. Wagner, <a href="http://siam.omnibooksonline.com/2012ANALCO/data/papers/001.pdf">Asymptotic enumeration of extensional acyclic digraphs</a>, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/01-Matrix.html">(0,1)-Matrix</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/AcyclicDigraph.html">Acyclic Digraph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PositiveEigenvaluedMatrix.html">Positive Eigenvalued Matrix</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/WeissteinsConjecture.html">Weisstein's Conjecture</a>

%H Chris Ying, <a href="https://arxiv.org/abs/1902.06192">Enumerating Unique Computational Graphs via an Iterative Graph Invariant</a>, arXiv:1902.06192 [cs.DM], 2019.

%H <a href="/index/Mat#binmat">Index entries for sequences related to binary matrices</a>

%F a(0) = 1; for n > 0, a(n) = Sum_{k=1..n} (-1)^(k+1)*C(n, k)*2^(k*(n-k))*a(n-k).

%F 1 = Sum_{n>=0} a(n)*exp(-2^n*x)*x^n/n!. - _Vladeta Jovovic_, Jun 05 2005

%F a(n) = Sum_{k=1..n} (-1)^(n-k)*A046860(n,k) = Sum_{k=1..n} (-1)^(n-k)*k!*A058843(n,k). - _Vladeta Jovovic_, Jun 20 2008

%F 1 = Sum_{n=>0} a(n)*x^n/(1 + 2^n*x)^(n+1). - _Paul D. Hanna_, Oct 17 2009

%F 1 = Sum_{n>=0} a(n)*C(n+m-1,n)*x^n/(1 + 2^n*x)^(n+m) for m>=1. - _Paul D. Hanna_, Apr 01 2011

%F log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 2^n*x)^n. - _Paul D. Hanna_, Apr 01 2011

%F Let E(x) = Sum_{n >= 0} x^n/(n!*2^C(n,2)). Then a generating function for this sequence is 1/E(-x) = Sum_{n >= 0} a(n)*x^n/(n!*2^C(n,2)) = 1 + x + 3*x^2/(2!*2) + 25*x^3/(3!*2^3) + 543*x^4/(4!*2^6) + ... (Stanley). Cf. A188457. - _Peter Bala_, Apr 01 2013

%F a(n) ~ n!*2^(n*(n-1)/2)/(M*p^n), where p = 1.488078545599710294656246... is the root of the equation Sum_{n>=0} (-1)^n*p^n/(n!*2^(n*(n-1)/2)) = 0, and M = Sum_{n>=1} (-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)) = 0.57436237330931147691667... Both references to the article "Acyclic digraphs and eigenvalues of (0,1)-matrices" give the wrong value M=0.474! - _Vaclav Kotesovec_, Dec 09 2013 [Response from _N. J. A. Sloane_, Dec 11 2013: The value 0.474 has a typo, it should have been 0.574. The value was taken from Stanley's 1973 paper.]

%F exp( Sum_{n >= 1} a(n)*x^n/n ) = 1 + x + 2*x^2 + 10*x^3 + 146*x^4 + 6010*x^5 + ... appears to have integer coefficients (cf. A188490). - _Peter Bala_, Jan 14 2016

%e For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.

%p p:=evalf(solve(sum((-1)^n*x^n/(n!*2^(n*(n-1)/2)), n=0..infinity) = 0, x), 50); M:=evalf(sum((-1)^(n+1)*p^n/((n-1)!*2^(n*(n-1)/2)), n=1..infinity), 40); # program for evaluation of constants p and M in the asymptotic formula, _Vaclav Kotesovec_, Dec 09 2013

%t a[0] = a[1] = 1; a[n_] := a[n] = Sum[ -(-1)^k * Binomial[n, k] * 2^(k*(n-k)) * a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 13}](* _Jean-François Alcover_, May 21 2012, after PARI *)

%t Table[2^(n*(n-1)/2)*n! * SeriesCoefficient[1/Sum[(-1)^k*x^k/k!/2^(k*(k-1)/2),{k,0,n}],{x,0,n}],{n,0,20}] (* _Vaclav Kotesovec_, May 19 2015 *)

%o (PARI) a(n)=if(n<1,n==0,sum(k=1,n,-(-1)^k*binomial(n,k)*2^(k*(n-k))*a(n-k)))

%o (PARI) {a(n)=polcoeff(1-sum(k=0, n-1, a(k)*x^k/(1+2^k*x+x*O(x^n))^(k+1)), n)} \\ _Paul D. Hanna_, Oct 17 2009

%Y Cf. A003087 (unlabeled DAGs), A086510, A081064 (refined by # arcs), A307049 (by # descents).

%Y Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which counts positive definite {0, 1} matrices.

%Y Cf. A188457, A135079, A137435 (acyclic 3-multidigraphs), A188490.

%K nonn,easy,nice

%O 0,3

%A _N. J. A. Sloane_

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 16 03:52 EDT 2022. Contains 356150 sequences. (Running on oeis4.)