|
|
A005512
|
|
Number of series-reduced labeled trees with n nodes.
(Formerly M3261)
|
|
9
|
|
|
1, 1, 0, 4, 5, 96, 427, 6448, 56961, 892720, 11905091, 211153944, 3692964145, 75701219608, 1613086090995, 38084386700896, 949168254452993, 25524123909350112, 725717102391257347, 21955114496683796680
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
a(n) = Sum_{k=0..n-2} (-1)^k*(n-k)^(n-k-2)*binomial(n, k)*(n-2)!/(n-k-2)!, n>=2.
|
|
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
|
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;
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|