|
%I M3113
%S 1,1,3,25,543,29281,3781503,1138779265,783702329343,1213442454842881,
%T 4175098976430598143,31603459396418917607425,
%U 521939651343829405020504063,18676600744432035186664816926721
%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.
%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. [From _Vladeta Jovovic_, Oct 28 2009]
%D 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; http://www.sci.kth.se/polopoly_fs/1.364961!/Menu/general/column-content/attachment/final_3_Random%20orientations.pdf.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).
%D Jack Kuipers and Giusi Moffa, Uniform generation of random acyclic digraphs, Arxiv preprint arXiv:1202.6590, 2012. - _N. J. A. Sloane_, Sep 14 2012
%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 I. Shpitser, T. S. Richardson, J. M. Robins and R. Evans, Parameter and Structure Learning in Nested Markov Models, Arxiv preprint arXiv:1207.5058, 2012. - From _N. J. A. Sloane_, Dec 23 2012
%D S. Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12); http://siam.omnibooksonline.com/2012ANALCO/data/papers/001.pdf
%H T. D. Noe, <a href="/A003024/b003024.txt">Table of n, a(n) for n=0..40</a>
%H 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 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 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 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 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/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 <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). [From _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 1 2011]
%F log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 2^n*x)^n. [Paul D. Hanna, Apr 1 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
%e For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.
%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 *)
%o (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 (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_, Oct 17 2009]
%Y Cf. A003087 (unlabeled DAGs), A086510.
%Y Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which counts positive definite {0, 1} matrices.
%Y Cf. A188457. A135079.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_.
|
