# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/
Search: id:a003024
Showing 1-1 of 1
%I A003024 M3113 #186 Aug 13 2024 04:12:38
%S A003024 1,1,3,25,543,29281,3781503,1138779265,783702329343,1213442454842881,
%T A003024 4175098976430598143,31603459396418917607425,
%U A003024 521939651343829405020504063,18676600744432035186664816926721,1439428141044398334941790719839535103,237725265553410354992180218286376719253505
%N A003024 Number of acyclic digraphs (or DAGs) with n labeled nodes.
%C A003024 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 A003024 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 A003024 Also the number of nilpotent elements in the semigroup of binary relations on [n]. - _Geoffrey Critzer_, May 26 2022
%C A003024 From _Gus Wiseman_, Jan 01 2024: (Start)
%C A003024 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 A003024 {{1},{2},{3}}
%C A003024 {{1},{2},{1,3}}
%C A003024 {{1},{2},{1,2,3}}
%C A003024 {{1},{1,2},{1,3}}
%C A003024 {{1},{1,2},{2,3}}
%C A003024 {{1},{1,2},{1,2,3}}
%C A003024 These set-systems have ranks A367908, subset of A367906, for multisets A368101.
%C A003024 The version for no ways is A368600, any length A367903, ranks A367907.
%C A003024 The version for at least one way is A368601, any length A367902.
%C A003024 (End)
%D A003024 Archer, K., Gessel, I. M., Graves, C., & Liang, X. (2020). Counting acyclic and strong digraphs by descents. Discrete Mathematics, 343(11), 112041.
%D A003024 S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 310.
%D A003024 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).
%D A003024 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 A003024 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A003024 R. P Stanley, Enumerative Combinatorics I, 2nd. ed., p. 322.
%H A003024 Alois P. Heinz, Table of n, a(n) for n = 0..77 (first 41 terms from T. D. Noe)
%H A003024 T. E. Allen, J. Goldsmith, and N. Mattei, Counting, Ranking, and Randomly Generating CP-nets, 2014.
%H A003024 Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
%H A003024 Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
%H A003024 Eunice Y.-J. Chen, A. Choi, and A. Darwiche, On Pruning with the MDL Score, JMLR: Workshop and Conference Proceedings vol 52, 98-109, 2016.
%H A003024 S. Engstrom, Random acyclic orientations of graphs, Master's thesis written at the department of Mathematics at the Royal Institute of Technology (KTH) in Stockholm, Jan. 2013.
%H A003024 Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See p. 33.
%H A003024 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
%H A003024 Laphou Lao, Zecheng Li, Songlin Hou, Bin Xiao, Songtao Guo, and Yuanyuan Yang, A Survey of IoT Applications in Blockchain Systems: Architecture, Consensus and Traffic Modeling, ACM Computing Surveys (CSUR, 2020) Vol. 53, No. 1, Article No. 18.
%H A003024 Daniel Mallia, Towards an Unsupervised Bayesian Network Pipeline for Explainable Prediction, Decision Making and Discovery, Master's Thesis, CUNY Hunter College (2023).
%H A003024 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.
%H A003024 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], Oct 28 2003.
%H A003024 A. Motzek and R. Möller, Exploiting Innocuousness in Bayesian Networks, Preprint 2015.
%H A003024 Yisu Peng, Y. Jiang, and P. Radivojac, Enumerating consistent subgraphs of directed acyclic graphs: an insight into biomedical ontologies, arXiv preprint arXiv:1712.09679 [cs.DS], 2017.
%H A003024 J. Peters, J. Mooij, D. Janzing, and B. Schölkopf, Causal Discovery with Continuous Additive Noise Models, arXiv preprint arXiv:1309.6779 [stat.ML], 2013.
%H A003024 R. W. Robinson, Enumeration of acyclic digraphs, Manuscript. (Annotated scanned copy)
%H A003024 V. I. Rodionov, On the number of labeled acyclic digraphs, Disc. Math. 105 (1-3) (1992) 319-321
%H A003024 I. Shpitser, T. S. Richardson, J. M. Robins and R. Evans, Parameter and Structure Learning in Nested Markov Models, arXiv preprint arXiv:1207.5058 [stat.ML], 2012.
%H A003024 I. Shpitser, R. J. Evans, T. S. Richardson, and J. M. Robins, Introduction to nested Markov models, Behaviormetrika, Behaviormetrika Vol. 41, No. 1, 2014, 3-39.
%H A003024 R. P. Stanley, Acyclic orientation of graphs, Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
%H A003024 Christian Toth, Christian Knoll, Franz Pernkopf, and Robert Peharz, Rao-Blackwellising Bayesian Causal Inference, arXiv:2402.14781 [cs.LG], 2024.
%H A003024 Sumanth Varambally, Yi-An Ma, and Rose Yu, Discovering Mixtures of Structural Causal Models from Time Series Data, arXiv:2310.06312 [cs.LG], 2023.
%H A003024 S. Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).
%H A003024 Daniel Waxman, Kurt Butler, and Petar M. Djuric, Dagma-DCE: Interpretable, Non-Parametric Differentiable Causal Discovery, arXiv:2401.02930 [cs.LG], 2024.
%H A003024 Eric Weisstein's World of Mathematics, (0,1)-Matrix
%H A003024 Eric Weisstein's World of Mathematics, Acyclic Digraph
%H A003024 Eric Weisstein's World of Mathematics, Positive Eigenvalued Matrix
%H A003024 Eric Weisstein's World of Mathematics, Weisstein's Conjecture
%H A003024 Jun Wu and Mathias Drton, Partial Homoscedasticity in Causal Discovery with Linear Models, arXiv:2308.08959 [math.ST], 2023.
%H A003024 Chris Ying, Enumerating Unique Computational Graphs via an Iterative Graph Invariant, arXiv:1902.06192 [cs.DM], 2019.
%H A003024 Index entries for sequences related to binary matrices
%F A003024 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 A003024 1 = Sum_{n>=0} a(n)*exp(-2^n*x)*x^n/n!. - _Vladeta Jovovic_, Jun 05 2005
%F A003024 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 A003024 1 = Sum_{n=>0} a(n)*x^n/(1 + 2^n*x)^(n+1). - _Paul D. Hanna_, Oct 17 2009
%F A003024 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 A003024 log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 2^n*x)^n. - _Paul D. Hanna_, Apr 01 2011
%F A003024 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 A003024 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 A003024 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 A003024 For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.
%p A003024 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 A003024 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 A003024 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 A003024 Table[Length[Select[Subsets[Subsets[Range[n]],{n}],Length[Select[Tuples[#],UnsameQ@@#&]]==1&]],{n,0,5}] (* _Gus Wiseman_, Jan 01 2024 *)
%o A003024 (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 A003024 (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 A003024 Cf. A086510, A081064 (refined by # arcs), A307049 (by # descents).
%Y A003024 Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which counts positive definite {0, 1} matrices.
%Y A003024 Cf. A188457, A135079, A137435 (acyclic 3-multidigraphs), A188490.
%Y A003024 For a unique sink we have A003025.
%Y A003024 The unlabeled version is A003087.
%Y A003024 These are the reverse-alternating sums of rows of A046860.
%Y A003024 The weakly connected case is A082402.
%Y A003024 A reciprocal version is A334282.
%Y A003024 Row sums of A361718.
%Y A003024 Cf. A003465, A058877, A058891, A059201, A088957, A133686, A323818.
%K A003024 nonn,easy,nice
%O A003024 0,3
%A A003024 _N. J. A. Sloane_
# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE