A058877 - OEIS

%I #76 Feb 01 2024 12:10:19

%S 0,2,9,28,75,186,441,1016,2295,5110,11253,24564,53235,114674,245745,

%T 524272,1114095,2359278,4980717,10485740,22020075,46137322,96468969,

%U 201326568,419430375,872415206,1811939301,3758096356,7784628195,16106127330,33285996513

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

%C Convolution of 2^n+1 (A000051) and 2^n-1 (A000225). - _Graeme McRae_, Jun 07 2006

%C 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

%C Also: convolution of A006589 with A000012 (i.e., partial sums of A006589). - _R. J. Mathar_, Jan 25 2009

%C 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

%C 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

%C Column 1 of A198204. - _Peter Bala_, Aug 01 2012

%C 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

%C 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

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).

%D 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]

%H Vincenzo Librandi, <a href="/A058877/b058877.txt">Table of n, a(n) for n = 1..2001</a>

%H Jia Huang and Erkko Lehtonen, <a href="https://arxiv.org/abs/2401.15786">Associative-commutative spectra for some varieties of groupoids</a>, arXiv:2401.15786 [math.CO], 2024. See p. 12.

%H Han Mao Kiah, Alexander Vardy and Hanwen Yao, <a href="https://arxiv.org/abs/2107.07377">Computing Permanents on a Trellis</a>, arXiv:2107.07377 [cs.IT], 2021.

%H Szakács, Tamás <a href="https://doi.org/10.1515/cm-2017-0011">Convolution of second order linear recursive sequences. II.</a>  Commun. Math. 25, No. 2, 137-148 (2017), remark 3

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (6,-13,12,-4).

%F 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

%F From _R. J. Mathar_, Jan 25 2009: (Start)

%F G.f.: x^2*(2-3*x)/((1-2*x)*(1-x))^2.

%F a(n) = 6*a(n-1) - 13*a(n-2) + 12*a(n-3) - 4*a(n-4). (End)

%F a(n) = Sum_{k=1..n-1} binomial(n, k) * (n-k). - _Michael Somos_, Mar 29 2012

%F E.g.f: x*exp(x)*(exp(x)-1). - _Enrique Navarrete_, Apr 05 2021

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

%p [seq (stirling2(n,2)*n,n=1..29)]; # _Zerinvary Lajos_, Dec 06 2006

%p a:=n->sum(k*binomial(n,k), k=2..n): seq(a(n), n=1..29); # _Zerinvary Lajos_, May 08 2007

%t Table[(n+1)*2^n-n-1, {n, 0, 200}] (* _Vladimir Joseph Stephan Orlovsky_, Jun 30 2011 *)

%t a[ n_] := Sum[ Binomial[ n, k] (n - k), {k, n-1}]; (* _Michael Somos_, Mar 29 2012 *)

%o (Sage) [stirling_number2(i,2)*i for i in range(1,26)] # _Zerinvary Lajos_, Jun 27 2008

%o (Sage) [(n+1)*gaussian_binomial(n,1,2) for n in range(0,29)] # _Zerinvary Lajos_, May 31 2009

%o (Magma) [(n+1)*2^n-n-1: n in [0..30]]; // _Vincenzo Librandi_, Sep 26 2011

%o (PARI) {a(n) = if( n<1, 0, n * (2^(n-1) - 1))} /* _Michael Somos_, Mar 29 2012 */

%Y Second column of A058876. Cf. A003025, A003026.

%Y Column k=1 of A133399.

%Y Cf. A198204.

%K nonn,easy

%O 1,2

%A _N. J. A. Sloane_, Jan 07 2001

%E More terms from _Vladeta Jovovic_, Apr 10 2001