|
| |
|
|
A058877
|
|
Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero.
|
|
11
| |
|
|
0, 2, 9, 28, 75, 186, 441, 1016, 2295, 5110, 11253, 24564, 53235, 114674, 245745, 524272, 1114095, 2359278, 4980717, 10485740, 22020075, 46137322, 96468969, 201326568, 419430375, 872415206, 1811939301, 3758096356, 7784628195, 16106127330, 33285996513
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| Convolution of 2^n+1 (A000051) and 2^n-1 (A000225) - Graeme McRae (g_m(AT)mcraefamily.com), Jun 07 2006
Let Q be a binary relation on the power set P(A) of a set A having n = |A| elements such that for all non-empty elements x,y of P(A), xRy if x is a proper subset of y and there are no z in P(A) such that x is a proper subset of z and z is a proper subset of y. Then a(n) = |Q|. - Ross La Haye (rlahaye(AT)new.rr.com), Feb 20 2008
Also: convolution of A006589 with A000012 (i.e., partial sums of A006589). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jan 25 2009]
|
|
|
REFERENCES
| F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
Gerta Rucker and Christoph Rucker, "Walk counts, Labyrinthicity and complexity of acyclic and cyclic graphs and molecules", J. Chem. Inf. Comput. Sci., 40 (2000), 99-106. See Table 1 on page 101. [From Parthasarathy Nambi (PachaNambi(AT)yahoo.com), Sep 26 2008]
|
|
|
LINKS
| Vincenzo Librandi, Table of n, a(n) for n = 0..2000
|
|
|
FORMULA
| a(n) = (n+1)*2^n-n-1 = Sum{0 <= j <= n}[(n+j)*2^(n-j-1)] = A048493(n)-1 = Column sum of A062111. - Henry Bottomley (se16(AT)btinternet.com), May 30 2001
a:=sum(k*2^(k-2), k=2..n). - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Oct 09 2006
G.f.: x^2(2-3x)/((1-2x)(1-x))^2 . a(n)=6*a(n-1)-13*a(n-2)+12*a(n-3)-4*a(n-4). [From R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Jan 25 2009]
|
|
|
MAPLE
| [seq (stirling2(n, 2)*n, n=1..29)]; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Dec 06 2006
a:=n->sum(k*binomial(n, k), k=2..n): seq(a(n), n=1..29); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 08 2007
a:=n->sum(sum(binomial(n, j), j=1..n), k=0..n): seq(a(n), n=0..28); - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 08 2007
a:=n->1/2*sum(sum (2^j, j=1..n), k=0..n): seq(a(n), n=0..28; - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 27 2007
|
|
|
MATHEMATICA
| Table[(n+1)*2^n-n-1, {n, 0, 200}] (* From Vladimir Joseph Stephan Orlovsky, Jun 30 2011 *)
|
|
|
PROG
| sage: [stirling_number2(i, 2)*i for i in xrange(1, 26)] - Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), Jun 27 2008
(Other) sage: [(n+1)*gaussian_binomial(n, 1, 2) for n in xrange(0, 29)] # [From Zerinvary Lajos (zerinvarylajos(AT)yahoo.com), May 31 2009]
(MAGMA) [(n+1)*2^n-n-1: n in [0..30]]; // Vincenzo Librandi, Sep 26 2011
|
|
|
CROSSREFS
| Second column of A058876. Cf. A003025, A003026.
Column k=1 of A133399. [From Alois P. Heinz (heinz(AT)hs-heilbronn.de), Sep 19 2008]
Sequence in context: A121643 A183376 A131066 * A192693 A026087 A109188
Adjacent sequences: A058874 A058875 A058876 * A058878 A058879 A058880
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Jan 07 2001
|
|
|
EXTENSIONS
| More terms from Vladeta Jovovic (vladeta(AT)eunet.rs), Apr 10 2001
Corrected my comment of Feb 20 2008. I indicated that a(n-1) = |Q| when in fact a(n) = |Q|. - Ross La Haye (rlahaye(AT)new.rr.com), Oct 21 2008
Offset changed from 1 to 0 by Vincenzo Librandi, Sep 26 2011
|
| |
|
|
