cp's OEIS Frontend

A005512 Number of series-reduced labeled trees with n nodes.

%I A005512 M3261 #75 Feb 16 2025 08:32:28
%S A005512 1,1,0,4,5,96,427,6448,56961,892720,11905091,211153944,3692964145,
%T A005512 75701219608,1613086090995,38084386700896,949168254452993,
%U A005512 25524123909350112,725717102391257347,21955114496683796680
%N A005512 Number of series-reduced labeled trees with n nodes.
%D A005512 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 188 (3.1.94)
%D A005512 F. Harary and E. M. Palmer, Graphical Enumeration. New York: Academic Press, 1973. (gives g.f. for unlabeled series-reduced trees)
%D A005512 R. C. Read, personal communication.
%D A005512 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005512 T. D. Noe, <a href="/A005512/b005512.txt">Table of n, a(n) for n=1..100</a>
%H A005512 David Callan, <a href="http://arxiv.org/abs/1406.7784">A sign-reversing involution to count labeled lone-child-avoiding trees</a>, arXiv:1406.7784 [math.CO], (30-June-2014)
%H A005512 D. M. Jackson, <a href="/A005512/a005512.pdf">Letter to N. J. A. Sloane, May 1975</a>
%H A005512 P. Leroux and B. Miloudi, <a href="http://www.labmath.uqam.ca/~annales/volumes/16-1/PDF/053-080.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Quebec 16 (1992), no 1, 53-80.
%H A005512 P. Leroux and B. Miloudi, <a href="/A000081/a000081_2.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
%H A005512 A. Meir and J. W. Moon, <a href="http://dx.doi.org/10.1112/S0025579300002552">On nodes of degree two in random trees</a>, Mathematika 15 1968 188-192.
%H A005512 R. C. Read, <a href="http://dx.doi.org/10.1111/j.1749-6632.1970.tb56486.x">Some Unusual Enumeration Problems</a>, Annals of the New York Academy of Sciences, Vol. 175, 1970, 314-326.
%H A005512 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Series-ReducedTree.html">Series-reduced Tree</a>
%H A005512 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A005512 a(n) = A060313(n)/n.
%F A005512 a(n) = Sum_{k=0..n-2} (-1)^k*(n-k)^(n-k-2)*binomial(n, k)*(n-2)!/(n-k-2)!, n>=2.
%F A005512 E.g.f.: (1+x)*B(x)*(1-B(x)/2), where B(x) is e.g.f. for A060356. - _Vladeta Jovovic_, Dec 17 2004
%F A005512 a(n) ~ (1-exp(-1))^(n+1/2)*n^(n-2). - _Vaclav Kotesovec_, Aug 07 2013
%e A005512 a(6) = 96 because there are two unlabeled series-reduced trees on six vertices, the star and the tree with two vertices of degree three and four leaves; the first of these can be labeled in 6 ways and the second in 90, for a total of 96. - Isabel C. Lugo (izzycat(AT)gmail.com), Aug 19 2004
%p A005512 A005512 := proc(n)
%p A005512     if n = 1 then
%p A005512         1;
%p A005512     else
%p A005512         add( (-1)^(n-r)*binomial(n,r)*r^(r-2)/(r-2)!,r=2..n) ;
%p A005512         %*(n-2)! ;
%p A005512     end if;
%p A005512 end proc: # _R. J. Mathar_, Sep 09 2014
%t A005512 a[1] = a[2] = 1; a[3] = 0; a[n_] := n!*(n-2)!*Sum[ (-1)^k*(n-k)^(n-k-3) / (k!*(n-k-2)!^2*(n-k-1)), {k, 0, n-2}]; Table[a[n], {n, 1, 20}](* _Jean-François Alcover_, Feb 16 2012, after given formula *)
%t A005512 u[1, 1] = 1; u[2, 1] = 0; u[2, 2] = 1; u[3, k_] := 0;
%t A005512 u[n_, k_] /; k <= 0 := 0;
%t A005512 u[n_, k_] /; k >= 1 :=
%t A005512 u[n, k] = (n (n - k) u[n - 1, k - 1] + n (n - 1) (n - 3) u[n - 2, k - 1])/k;
%t A005512 Table[Sum[u[n, m], {m, 1, n}], {n, 50}] (* _David Callan_, Jun 25 2014, fast generation, after R. C. Read link *)
%o A005512 (PARI) a(n) = if(n<=1, n==1, sum(k=0, n-2, (-1)^k*(n-k)^(n-k-2)*binomial(n, k)*(n-2)!/(n-k-2)!)) \\ _Andrew Howroyd_, Dec 18 2017
%o A005512 (Magma) [1] cat [Factorial(n-2)*(&+[(-1)^k*Binomial(n,k)*(n-k)^(n-k-2)/Factorial(n-k-2): k in [0..n-2]]): n in [2..20]]
%o A005512 (Sage) [1]+[factorial(n-2)*sum((-1)^k*binomial(n,k)*(n-k)^(n-k-2)/factorial( n-k-2) for k in (0..n-2)) for n in (2..20)] # _G. C. Greubel_, Mar 07 2020
%Y A005512 Cf. A000014 (unlabeled analog), A060313.
%K A005512 nonn,nice
%O A005512 1,4
%A A005512 _N. J. A. Sloane_, _Simon Plouffe_
%E A005512 Formula from _Christian G. Bower_, Jan 16 2004