|
| |
|
|
A003024
|
|
Number of acyclic digraphs (or DAGs) with n labeled nodes.
(Formerly M3113)
|
|
20
| |
|
|
1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425, 521939651343829405020504063, 18676600744432035186664816926721
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| 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
| 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.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n=0..40
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions.
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
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]
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]
log(1+x) = Sum_{n>=1} a(n)*(x^n/n)/(1 + 2^n*x)^n. [Paul D. Hanna, Apr 1 2011]
|
|
|
EXAMPLE
| For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.
|
|
|
PROG
| (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.
Cf. A188457.
Sequence in context: A009843 A182962 A136173 * A179473 A131310 A127231
Adjacent sequences: A003021 A003022 A003023 * A003025 A003026 A003027
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
