|
Search: id:A003024
|
|
|
| A003024 |
|
Number of acyclic digraphs (or DAGs) with n labeled nodes.
(Formerly M3113)
|
|
+0
16
|
|
| 1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425, 521939651343829405020504063, 18676600744432035186664816926721
(list; graph; listen)
|
|
|
OFFSET
|
0,3
|
|
|
COMMENT
|
Also the number of n X n real (0,1)-matrices with all eigenvalues positive.
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]
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).
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.
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=0..40
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.
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
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions.
Eric Weisstein's World of Mathematics, Positive Eigenvalued Matrix
Eric Weisstein's World of Mathematics, (0,1)-Matrix
Eric Weisstein's World of Mathematics, Acyclic Digraph
Index entries for sequences related to binary matrices
|
|
FORMULA
|
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).
1 = Sum_{n>=0} a(n)*exp(-2^n*x)*x^n/n!. - Vladeta Jovovic (vladeta(AT)eunet.rs), Jun 05 2005
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
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]
|
|
EXAMPLE
|
For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.
|
|
PROGRAM
|
(PARI) a(n)=if(n<1, n==0, sum(k=1, n, -(-1)^k*C(n, k)*2^(k*(n-k))*a(n-k)))
(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]
|
|
CROSSREFS
|
Cf. A003087 (unlabeled DAGs), A086510.
Cf. A055165, which counts nonsingular {0, 1} matrices and A085656, which counts positive definite {0, 1} matrices.
Sequence in context: A160143 A009843 A136173 this_sequence A131310 A127231 A062411
Adjacent sequences: A003021 A003022 A003023 this_sequence A003025 A003026 A003027
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
Search completed in 0.002 seconds
|
