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
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
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
Formula from Christian G. Bower, Jan 16 2004
STATUS
approved