A000554 Number of labeled trees of diameter 3 with n nodes.

12, 60, 210, 630, 1736, 4536, 11430, 28050, 67452, 159588, 372554, 859950, 1965840, 4456176, 10026702, 22412970, 49806980, 110100060, 242220594, 530578950, 1157627352, 2516581800, 5452594550, 11777604930, 25367149836, 54492396756, 116769422490, 249644973150

Offset: 4

Author

N. J. A. Sloane

Keywords

• nonn
• easy

References

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

Links

• Colin Barker, Table of n, a(n) for n = 4..1000
• J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
• Index entries for sequences related to trees
• Index entries for linear recurrences with constant coefficients, signature (9,-33,63,-66,36,-8).

Programs

Mathematica

f[n_] := n (n - 1)*StirlingS2[n - 2, 2]; Table[ f@n, {n, 4, 29}] (* Robert G. Wilson v, Jul 01 2007 *)

PARI

Vec(2*x^4*(6-24*x+33*x^2-18*x^3+4*x^4)/((1-x)^3*(1-2*x)^3) + O(x^40)) \\ Colin Barker, Sep 18 2016

Formula

a(n) = n(n-1)*S2(n-2, 2) where S2(n, k) denotes the Stirling numbers of 2nd kind. - Victor Adamchik (adamchik(AT)cs.cmu.edu), Jul 19 2001

a(n) = n*(n-1)*(2^(n-3) - 1) = 2*A000217(n-1)*A000225(n-3). - Robert G. Wilson v, Jul 01 2007, corrected by Ilya Gutkovskiy, Sep 17 2016

a(n) = Sum_{k=1..n-3} binomial(n,2)*binomial(n-2,k). The sum gives the number of Prüfer sequences with exactly 2 distinct digits. - Geoffrey Critzer, Sep 17 2016

E.g.f.: (x*(exp(x)-1))^2/2. - Geoffrey Critzer, Sep 17 2016

O.g.f.: 2*x^4*(6 - 24*x + 33*x^2 - 18*x^3 + 4*x^4)/((1 - x)^3*(1 - 2*x)^3). - Ilya Gutkovskiy, Sep 17 2016

a(n) = (2^n-8)*(n-1)*n/8. - Colin Barker, Sep 18 2016

Extensions

More terms from Robert G. Wilson v, Jul 01 2007