|
|
A005198
|
|
a(n) is the number of forests with n (unlabeled) nodes in which each component tree is planted, that is, is a rooted tree in which the root has degree 1.
(Formerly M2491)
|
|
2
|
|
|
0, 1, 1, 3, 5, 13, 27, 68, 160, 404, 1010, 2604, 6726, 17661, 46628, 124287, 333162, 898921, 2437254, 6640537, 18166568, 49890419, 137478389, 380031868, 1053517588, 2928246650, 8158727139, 22782938271, 63752461474, 178740014515, 502026565792, 1412409894224
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
|
|
FORMULA
|
a(1) = 0, if n >= 2 a(n) = Sum_{P_1(n)}( Product_{k=2..n} binomial(A000081(k-1) + c_k - 1, c_k) ), where P_1(n) are the partitions of n without parts equal to 1: 2*c_2 + ... + n*c_n = n; c_2, ..., c_n >= 0. - Washington Bomfim, Jul 05 2020
|
|
MAPLE
|
g:= proc(n) option remember; `if`(n<=1, n, (add(add(d*g(d),
d=numtheory[divisors](j))*g(n-j), j=1..n-1))/(n-1))
end:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<2, 0, add(
binomial(g(i-1)+j-1, j)*b(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> b(n$2):
|
|
MATHEMATICA
|
g[n_] := g[n] = If[n <= 1, n, Sum[Sum[d g[d], {d, Divisors[j]}] g[n - j], {j, 1, n - 1}]/(n - 1)];
b[n_, i_] := b[n, i] = If[n == 0, 1, If[i < 2, 0, Sum[Binomial[g[i - 1] + j - 1, j] b[n - i j, i - 1], {j, 0, n/i}]]];
a[n_] := b[n, n];
|
|
PROG
|
(PARI) g(m) = {my(f); if(m==0, return(1)); f = vector(m+1); f[1]=1;
for(j=1, m, f[j+1]=1/j * sum(k=1, j, sumdiv(k, d, d * f[d]) * f[j-k+1])); f[m+1] };
global(max_n = 130); A000081 = vector(max_n, n, g(n-1));
seq(n)={my(s=0, D, c, P_1); if(n==1, return(0)); forpart(P_1 = n, D = Set(P_1); c = vector(#D); for(k=1, #D, c[k] = #select(x->x == D[k], Vec(P_1)));
s += prod(k=1, #D, binomial( A000081[D[k]-1] + c[k] - 1, c[k]) ), [2, n], [1, n]); s}; \\ Washington Bomfim, Jul 05 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Definition clarified and more terms added from Palmer-Schwenk by N. J. A. Sloane, May 29 2012
|
|
STATUS
|
approved
|
|
|
|