This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A058877 Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero. 14
 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; text; internal format)
 OFFSET 1,2 COMMENTS Convolution of 2^n+1 (A000051) and 2^n-1 (A000225). - Graeme McRae, 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 nonempty 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, Feb 20 2008, Oct 21 2008 Also: convolution of A006589 with A000012 (i.e., partial sums of A006589). - R. J. Mathar, Jan 25 2009 The La Haye binary relation Q is more clearly stated as x is nonempty and y has one more element than x. If x is a k-set than the number of such pairs is binomial( n, k) * (n-k). - Michael Somos, Mar 29 2012 Select one of the n nodes of the digraph and select a nonempty subset of the rest to connect to the selected node. This can be done in n * (2^(n-1) - 1) ways. - Michael Somos, Mar 29 2012 Column 1 of A198204. - Peter Bala, Aug 01 2012 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, Sep 26 2008] LINKS Vincenzo Librandi, Table of n, a(n) for n = 1..2001 Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4). FORMULA a(n+1) = (n+1)*2^n - n - 1 = Sum_{j=0..n} (n+j)*2^(n-j-1) = A048493(n)-1 = Column sum of A062111. - Henry Bottomley, May 30 2001 From R. J. Mathar, Jan 25 2009: (Start) 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). (End) a(n) = Sum_{k=1..n-1} binomial(n, k) * (n-k). - Michael Somos, Mar 29 2012 EXAMPLE G.f. = 2*x^2 + 9*x^3 + 28*x^4 + 75*x^5 + 186*x^6 + 441*x^7 + 1016*x^8 + ... MAPLE [seq (stirling2(n, 2)*n, n=1..29)]; # Zerinvary Lajos, Dec 06 2006 a:=n->sum(k*binomial(n, k), k=2..n): seq(a(n), n=1..29); # Zerinvary Lajos, May 08 2007 a:=n->sum(sum(binomial(n, j), j=1..n), k=0..n): seq(a(n), n=0..28); # Zerinvary Lajos, 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, Jun 27 2007 MATHEMATICA Table[(n+1)*2^n-n-1, {n, 0, 200}] (* Vladimir Joseph Stephan Orlovsky, Jun 30 2011 *) a[ n_] := Sum[ Binomial[ n, k] (n - k), {k, n-1}]; (* Michael Somos, Mar 29 2012 *) PROG (Sage) [stirling_number2(i, 2)*i for i in xrange(1, 26)] # Zerinvary Lajos, Jun 27 2008 (Sage) [(n+1)*gaussian_binomial(n, 1, 2) for n in xrange(0, 29)] # Zerinvary Lajos, May 31 2009 (MAGMA) [(n+1)*2^n-n-1: n in [0..30]]; // Vincenzo Librandi, Sep 26 2011 (PARI) {a(n) = if( n<1, 0, n * (2^(n-1) - 1))} /* Michael Somos, Mar 29 2012 */ CROSSREFS Second column of A058876. Cf. A003025, A003026. Column k=1 of A133399. Cf. A198204. Sequence in context: A121643 A183376 A131066 * A192693 A258347 A323957 Adjacent sequences:  A058874 A058875 A058876 * A058878 A058879 A058880 KEYWORD nonn,easy AUTHOR N. J. A. Sloane, Jan 07 2001 EXTENSIONS More terms from Vladeta Jovovic, Apr 10 2001 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified June 17 16:56 EDT 2019. Contains 324196 sequences. (Running on oeis4.)