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



Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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

%I M3113 #160 Oct 18 2023 11:50:59

%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 Alois P. Heinz, <a href="/A003024/b003024.txt">Table of n, a(n) for n = 0..77</a> (first 41 terms from T. D. Noe)

%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 Daniel Mallia, <a href="https://academicworks.cuny.edu/cgi/viewcontent.cgi?article=2063&amp;context=hc_sas_etds">Towards an Unsupervised Bayesian Network Pipeline for Explainable Prediction, Decision Making and Discovery</a>, Master's Thesis, CUNY Hunter College (2023).

%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 Sumanth Varambally, Yi-An Ma, and Rose Yu, <a href="https://arxiv.org/abs/2310.06312">Discovering Mixtures of Structural Causal Models from Time Series Data</a>, arXiv:2310.06312 [cs.LG], 2023.

%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 Jun Wu and Mathias Drton, <a href="https://arxiv.org/abs/2308.08959">Partial Homoscedasticity in Causal Discovery with Linear Models</a>, arXiv:2308.08959 [math.ST], 2023.

%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 December 5 23:11 EST 2023. Contains 367594 sequences. (Running on oeis4.)