|
%I M3113 #178 Feb 26 2024 17:08:46
%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
%C From _Gus Wiseman_, Jan 01 2024: (Start)
%C Also the number of sets of n nonempty subsets of {1..n} such that there is a unique way to choose a different element from each. For example, non-isomorphic representatives of the a(3) = 25 set-systems are:
%C {{1},{2},{3}}
%C {{1},{2},{1,3}}
%C {{1},{2},{1,2,3}}
%C {{1},{1,2},{1,3}}
%C {{1},{1,2},{2,3}}
%C {{1},{1,2},{1,2,3}}
%C These set-systems have ranks A367908, subset of A367906, for multisets A368101.
%C The version for no ways is A368600, any length A367903, ranks A367907.
%C The version for at least one way is A368601, any length A367902.
%C (End)
%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&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 Christian Toth, Christian Knoll, Franz Pernkopf, and Robert Peharz, <a href="https://arxiv.org/abs/2402.14781">Rao-Blackwellising Bayesian Causal Inference</a>, arXiv:2402.14781 [cs.LG], 2024.
%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 Daniel Waxman, Kurt Butler, and Petar M. Djuric, <a href="https://arxiv.org/abs/2401.02930">Dagma-DCE: Interpretable, Non-Parametric Differentiable Causal Discovery</a>, arXiv:2401.02930 [cs.LG], 2024.
%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 *)
%t Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,5}] (* _Gus Wiseman_, Jan 01 2024 *)
%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. 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.
%Y For a unique sink we have A003025.
%Y The unlabeled version is A003087.
%Y These are the reverse-alternating sums of rows of A046860.
%Y The weakly connected case is A082402.
%Y A reciprocal version is A334282.
%Y Row sums of A361718.
%Y Cf. A003465, A058877, A058891, A059201, A088957, A133686, A323818.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
|
