%I A003024 M3113
%S A003024 1,1,3,25,543,29281,3781503,1138779265,783702329343,1213442454842881,
%T A003024 4175098976430598143,31603459396418917607425,
%U A003024 521939651343829405020504063,18676600744432035186664816926721
%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.
%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. [From Vladeta 
               Jovovic (vladeta(AT)eunet.rs), Oct 28 2009]
%D A003024 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%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.
%H A003024 T. D. Noe, <a href="b003024.txt">Table of n, a(n) for n=0..40</a>
%H A003024 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/
               index.html">Acyclic digraphs and eigenvalues of (0,1)-matrices</a>
               , 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, <a href="http://arXiv.org/abs/math.CO/0310423">Acyclic 
               digraphs and eigenvalues of (0,1)-matrices</a>
%H A003024 Huantian Cao, <a href="http://www.cs.uga.edu/~rwr/STUDENTS/hcao.html">
               AutoGF: An Automated System to Calculate Coefficients of Generating 
               Functions</a>.
%H A003024 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               PositiveEigenvaluedMatrix.html">Positive Eigenvalued Matrix</a>
%H A003024 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               01-Matrix.html">(0,1)-Matrix</a>
%H A003024 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/
               AcyclicDigraph.html">Acyclic Digraph</a>
%H A003024 <a href="Sindx_Mat.html#binmat">Index entries for sequences related to 
               binary matrices</a>
%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 (vladeta(AT)eunet.rs), 
               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 (vladeta(AT)eunet.rs), Jun 20 2008
%F A003024 1 = Sum_{n=>0} a(n)*x^n/(1 + 2^n*x)^(n+1). [From Paul D. Hanna (pauldhanna(AT)juno.com), 
               Oct 17 2009]
%e A003024 For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 
               1}}, {{1, 1}, {0, 1}}}.
%o A003024 (PARI) a(n)=if(n<1,n==0,sum(k=1,n,-(-1)^k*C(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)} [From Paul D. Hanna (pauldhanna(AT)juno.com), Oct 17 2009]
%Y A003024 Cf. A003087 (unlabeled DAGs), A086510.
%Y A003024 Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which 
               counts positive definite {0, 1} matrices.
%Y A003024 Sequence in context: A160143 A009843 A136173 this_sequence A131310 A127231 
               A062411
%Y A003024 Adjacent sequences: A003021 A003022 A003023 this_sequence A003025 A003026 
               A003027
%K A003024 nonn,easy,nice
%O A003024 0,3
%A A003024 N. J. A. Sloane (njas(AT)research.att.com).