A005512 Number of series-reduced labeled trees with n nodes. (Formerly M3261)

1, 1, 0, 4, 5, 96, 427, 6448, 56961, 892720, 11905091, 211153944, 3692964145, 75701219608, 1613086090995, 38084386700896, 949168254452993, 25524123909350112, 725717102391257347, 21955114496683796680

Offset

1,4

References

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 188 (3.1.94)

F. Harary and E. M. Palmer, Graphical Enumeration. New York: Academic Press, 1973. (gives g.f. for unlabeled series-reduced trees)

R. C. Read, personal communication.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

T. D. Noe, Table of n, a(n) for n=1..100

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)

D. M. Jackson, Letter to N. J. A. Sloane, May 1975

P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Quebec 16 (1992), no 1, 53-80.

P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)

A. Meir and J. W. Moon, On nodes of degree two in random trees, Mathematika 15 1968 188-192.

R. C. Read, Some Unusual Enumeration Problems, Annals of the New York Academy of Sciences, Vol. 175, 1970, 314-326.

Eric Weisstein's World of Mathematics, Series-reduced Tree

Index entries for sequences related to trees

Formula

a(n) = A060313(n)/n.

a(n) = Sum_{k=0..n-2} (-1)^k*(n-k)^(n-k-2)*binomial(n, k)*(n-2)!/(n-k-2)!, n>=2.

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

a(n) ~ (1-exp(-1))^(n+1/2)*n^(n-2). - Vaclav Kotesovec, Aug 07 2013

Example

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

Maple

A005512 := proc(n)
    if n = 1 then
        1;
    else
        add( (-1)^(n-r)*binomial(n, r)*r^(r-2)/(r-2)!, r=2..n) ;
        %*(n-2)! ;
    end if;
end proc: # R. J. Mathar, Sep 09 2014

Mathematica

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 *)
u[1, 1] = 1; u[2, 1] = 0; u[2, 2] = 1; u[3, k_] := 0;
u[n_, k_] /; k <= 0 := 0;
u[n_, k_] /; k >= 1 :=
u[n, k] = (n (n - k) u[n - 1, k - 1] + n (n - 1) (n - 3) u[n - 2, k - 1])/k;
Table[Sum[u[n, m], {m, 1, n}], {n, 50}] (* David Callan, Jun 25 2014, fast generation, after R. C. Read link *)

Prog

(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
(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]]
(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

Crossrefs

Cf. A000014 (unlabeled analog), A060313.

Sequence in context: A376048 A078985 A041173 * A331584 A052320 A079197

Adjacent sequences: A005509 A005510 A005511 * A005513 A005514 A005515

Keyword

nonn,nice

Author

N. J. A. Sloane, Simon Plouffe

Extensions

Formula from Christian G. Bower, Jan 16 2004

Status

approved