|
%I #55 Aug 22 2022 04:48:46
%S 1,1,3,16,120,1170,14070,201600,3356640,63730800,1359666000,
%T 32212857600,839350512000,23860289653200,734964075846000,
%U 24388126963200000,867393811956672000,32919980214689568000
%N Number of trees on n labeled vertices with degree at most 3.
%H Mathematics Stack Exchange, Marko Riedel et al., <a href="http://math.stackexchange.com/questions/1816933/">Number of labeled trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F E.g.f.: ((1-x)*(2-x-x^2) - (2-x+x^2)*sqrt(1-2*x-x^2)) / (3*x^3). [edited by _Franklin T. Adams-Watters_, May 24 2010]
%F The number of labeled trees with d[i] vertices of degree i for i=1,2,3 is (n-2)! * n! / (2^d[3] * d[3]! * d[2]! * d[1]!). Now sum over d[1]+d[2]+d[3]=n, d[1]+2*d[2]+3*d[3] = 2n-2. - _Brendan McKay_, May 24 2010; corrected Sep 17 2012.
%F From _Georgi Guninski_, May 24 2010: (Start)
%F The following relation seems to hold up to 3000 terms:
%F a(n+1) = (-a(n-1)*a(n) - (-3*a(n)^2 + (2/3)*a(n-2)*a(n)*n+ (-4/3)*a(n-1) *a(n)*n+ (-4/3)*a(n)^2*n+ (-1/3)*a(n-2)*a(n)*n^2+ (-2/3)*a(n-1)*a(n)* n^2)) / (a(n-1)+ (-1/3)*a(n) -2*a(n-2)*n+ 2*a(n-1)*n+a(n-2)*n^2). (End)
%F Recurrence: (n+3)*a(n) = (n+1)*(2*n+1)*a(n-1) + (n-2)*n*(n+1)*a(n-2). - _Vaclav Kotesovec_, Oct 07 2013
%F a(n) ~ (2-sqrt(2))^(3/2) * (1+sqrt(2))^(n+3) * n^(n-1) / exp(n). - _Vaclav Kotesovec_, Oct 07 2013
%F a(n) = Sum_{q=0..floor((n-2)/2)} C(n,q)*C(n-q,n-2-2q)*(n-2)!/2^q, a(n) = (n-2)!/2^n * Sum_{q=0..n} C(n,q) C(2q,n-2), a(n) = (n-2)!/2^n [v^{n-2}] (2+2v+v^2)^n. - _Marko Riedel_, Jun 10 2016
%t CoefficientList[Series[((1-x)*(2-x-x^2) - (2-x+x^2)*Sqrt[1-2*x-x^2]) / (3*x^3), {x, 0, 20}], x]* Range[0, 20]! (* _Vaclav Kotesovec_, Oct 07 2013 *)
%o (Sage)
%o gf = ((1-x)*(2-x-x^2) - (2-x+x^2)*(1-2*x-x^2)^(1/2)) / (3*x^3)
%o c = taylor(gf, x, 0, 12).coefficients()
%o sq = [a*factorial(b) for a, b in c]
%o sq
%o # _D. S. McNeil_, May 24 2010
%Y Cf. A000272, A274056, A274081, A274083.
%K nonn
%O 0,3
%A Alex Postnikov (apost(AT)math.mit.edu)
%E More terms from _Franklin T. Adams-Watters_, May 24 2010
| 