|
| |
|
|
A003024
|
|
Number of acyclic digraphs (or DAGs) with n labeled nodes.
(Formerly M3113)
|
|
23
|
|
|
|
1, 1, 3, 25, 543, 29281, 3781503, 1138779265, 783702329343, 1213442454842881, 4175098976430598143, 31603459396418917607425, 521939651343829405020504063, 18676600744432035186664816926721
(list;
graph;
refs;
listen;
history;
text;
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, Oct 28 2009]
|
|
|
REFERENCES
|
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.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, Eq. (1.6.1).
Jack Kuipers and Giusi Moffa, Uniform generation of random acyclic digraphs, Arxiv preprint arXiv:1202.6590, 2012. - N. J. A. Sloane, Sep 14 2012
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).
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
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
|
|
|
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
R. P. Stanley, Acyclic orientation of graphs Discrete Math. 5 (1973), 171-178. North Holland Publishing Company.
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, 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, Jun 20 2008
1 = Sum_{n=>0} a(n)*x^n/(1 + 2^n*x)^(n+1). [From Paul D. Hanna, 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]
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
|
|
|
EXAMPLE
|
For n = 2 the three (0,1)-matrices are {{{1, 0}, {0, 1}}, {{1, 0}, {1, 1}}, {{1, 1}, {0, 1}}}.
|
|
|
MATHEMATICA
|
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 *)
|
|
|
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, 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. A135079.
Sequence in context: A182962 A223076 A136173 * A224679 A213599 A179473
Adjacent sequences: A003021 A003022 A003023 * A003025 A003026 A003027
|
|
|
KEYWORD
|
nonn,easy,nice,changed
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
STATUS
|
approved
|
| |
|
|
