cp's OEIS Frontend

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

%I A058877 #80 Nov 14 2024 15:16:26
%S A058877 0,2,9,28,75,186,441,1016,2295,5110,11253,24564,53235,114674,245745,
%T A058877 524272,1114095,2359278,4980717,10485740,22020075,46137322,96468969,
%U A058877 201326568,419430375,872415206,1811939301,3758096356,7784628195,16106127330,33285996513
%N A058877 Number of labeled acyclic digraphs with n nodes containing exactly n-1 points of in-degree zero.
%C A058877 Convolution of 2^n+1 (A000051) and 2^n-1 (A000225). - _Graeme McRae_, Jun 07 2006
%C A058877 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 A058877 Also: convolution of A006589 with A000012 (i.e., partial sums of A006589). - _R. J. Mathar_, Jan 25 2009
%C A058877 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 A058877 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 A058877 Column 1 of A198204. - _Peter Bala_, Aug 01 2012
%C A058877 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 A058877 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 A058877 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 19, (1.6.4).
%D A058877 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 A058877 Vincenzo Librandi, <a href="/A058877/b058877.txt">Table of n, a(n) for n = 1..2001</a>
%H A058877 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 A058877 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 A058877 Tamás Szakács, <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 A058877 Tamás Szakács, <a href="https://hdl.handle.net/2437/381856">Linear recursive sequences and factorials</a>, Ph. D. Thesis, Univ. Debrecen (Hungary, 2024). See p. 36.
%H A058877 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (6,-13,12,-4).
%F A058877 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 A058877 From _R. J. Mathar_, Jan 25 2009: (Start)
%F A058877 G.f.: x^2*(2-3*x)/((1-2*x)*(1-x))^2.
%F A058877 a(n) = 6*a(n-1) - 13*a(n-2) + 12*a(n-3) - 4*a(n-4). (End)
%F A058877 a(n) = Sum_{k=1..n-1} binomial(n, k) * (n-k). - _Michael Somos_, Mar 29 2012
%F A058877 E.g.f: x*exp(x)*(exp(x)-1). - _Enrique Navarrete_, Apr 05 2021
%e A058877 G.f. = 2*x^2 + 9*x^3 + 28*x^4 + 75*x^5 + 186*x^6 + 441*x^7 + 1016*x^8 + ...
%p A058877 [seq (stirling2(n,2)*n,n=1..29)]; # _Zerinvary Lajos_, Dec 06 2006
%p A058877 a:=n->sum(k*binomial(n,k), k=2..n): seq(a(n), n=1..29); # _Zerinvary Lajos_, May 08 2007
%t A058877 Table[(n+1)*2^n-n-1, {n, 0, 200}] (* _Vladimir Joseph Stephan Orlovsky_, Jun 30 2011 *)
%t A058877 a[ n_] := Sum[ Binomial[ n, k] (n - k), {k, n-1}]; (* _Michael Somos_, Mar 29 2012 *)
%o A058877 (Sage) [stirling_number2(i,2)*i for i in range(1,26)] # _Zerinvary Lajos_, Jun 27 2008
%o A058877 (Sage) [(n+1)*gaussian_binomial(n,1,2) for n in range(0,29)] # _Zerinvary Lajos_, May 31 2009
%o A058877 (Magma) [(n+1)*2^n-n-1: n in [0..30]]; // _Vincenzo Librandi_, Sep 26 2011
%o A058877 (PARI) {a(n) = if( n<1, 0, n * (2^(n-1) - 1))} /* _Michael Somos_, Mar 29 2012 */
%Y A058877 Second column of A058876. Cf. A003025, A003026.
%Y A058877 Column k=1 of A133399.
%Y A058877 Cf. A198204.
%K A058877 nonn,easy
%O A058877 1,2
%A A058877 _N. J. A. Sloane_, Jan 07 2001
%E A058877 More terms from _Vladeta Jovovic_, Apr 10 2001