A058877 Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero.

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

Offset: 1

Author

N. J. A. Sloane, Jan 07 2001

Keywords

• nonn
• easy

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

a(n) is the number of ternary sequences of length n that contain one 0 and at least one 1. For example, a(3)=9 since the sequences are the 3 permutations of 011 and the 6 permutations of 012. - Enrique Navarrete, Apr 05 2021

a(n) is also the number of multiplications required to compute the permanent of general n X n matrices using canonical trellis method (see Theorem 5, p. 10 in Kiah et al.). - Stefano Spezia, Nov 02 2021

Examples

			G.f. = 2*x^2 + 9*x^3 + 28*x^4 + 75*x^5 + 186*x^6 + 441*x^7 + 1016*x^8 + ...
		

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
• Jia Huang and Erkko Lehtonen, Associative-commutative spectra for some varieties of groupoids, arXiv:2401.15786 [math.CO], 2024. See p. 12.
• Han Mao Kiah, Alexander Vardy and Hanwen Yao, Computing Permanents on a Trellis, arXiv:2107.07377 [cs.IT], 2021.
• Tamás Szakács, Convolution of second order linear recursive sequences. II. Commun. Math. 25, No. 2, 137-148 (2017), remark 3.
• Tamás Szakács, Linear recursive sequences and factorials, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See p. 36.
• Index entries for linear recurrences with constant coefficients, signature (6,-13,12,-4).

Crossrefs

Second column of A058876. Cf. A003025, A003026.

Column k=1 of A133399.

Cf. A198204.

Programs

Magma

[(n+1)*2^n-n-1: n in [0..30]]; // Vincenzo Librandi, Sep 26 2011

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

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 *)

PARI

{a(n) = if( n<1, 0, n * (2^(n-1) - 1))} /* Michael Somos, Mar 29 2012 */

Sage

[stirling_number2(i,2)*i for i in range(1,26)] # Zerinvary Lajos, Jun 27 2008

Sage

[(n+1)*gaussian_binomial(n,1,2) for n in range(0,29)] # Zerinvary Lajos, May 31 2009

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-3*x)/((1-2*x)*(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

E.g.f: x*exp(x)*(exp(x)-1). - Enrique Navarrete, Apr 05 2021

Extensions

More terms from Vladeta Jovovic, Apr 10 2001