|
|
A052827
|
|
a(n) is the number of unlabeled forests of rooted trees with n nodes such that no two trees are identical.
|
|
1
|
|
|
1, 1, 1, 3, 6, 15, 36, 90, 225, 578, 1492, 3901, 10278, 27313, 73042, 196585, 531847, 1445991, 3948282, 10823524, 29776129, 82183115, 227501127, 631494797, 1757297207, 4901491697, 13700742034, 38373104938, 107675540083, 302664162746, 852138516321, 2402817160804
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
Previous name was: "A simple grammar".
a(n) is the number of unlabeled forests of rooted trees with n nodes such that no two trees are identical. Example: a(4)=6 counts two different forests with 2 trees (1 tree on 1 node and one tree on 3 nodes splitting in two different ways) plus 4 different forests with 1 tree on 4 nodes (as counted by A000081(4)). - Geoffrey Critzer, Feb 21 2012.
|
|
LINKS
|
|
|
FORMULA
|
G.f.: A(x) = x*T(x)/T(x^2) = exp(T(x) - T(x^2)/2 + T(x^3)/3 - T(x^4)/4 +-...) where T(x) = g.f. of A000081 (number of rooted trees with n nodes). - Paul D. Hanna, Jul 13 2006
|
|
EXAMPLE
|
A(x) = 1 + x + x^2 + 3*x^3 + 6*x^4 + 15*x^5 + 36*x^6 + 90*x^7 +...
|
|
MAPLE
|
spec := [S, {B=Set(C), C=Prod(B, Z), S=PowerSet(C)}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
# second Maple program:
with(numtheory):
b:= proc(n) option remember; `if`(n<=1, n, (add(add(
d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))
end:
g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(binomial(b(i), j)*g(n-i*j, i-1), j=0..n/i)))
end:
a:= n-> g(n$2):
|
|
MATHEMATICA
|
max = 31; a81[0]=0; a81[1]=1; a81[n_] := a81[n] = Sum[DivisorSum[j, #*a81[ #]&] a81[n-j], {j, 1, n-1}]/(n-1); CoefficientList[Product[(1 + x^k)^a81[ k], {k, 1, max}] + O[x]^max, x] (* Jean-François Alcover, Feb 19 2016, after Vladeta Jovovic *)
|
|
PROG
|
(PARI) {a(n)=local(T=x+x*O(x^n)); if(n==0, 1, for(i=1, n, T=x*exp(sum(k=1, n, subst(T, x, x^k+x*O(x^n))/k))); polcoeff(x*T/subst(T, x, x^2), n, x))} \\ Paul D. Hanna, Jul 13 2006
|
|
CROSSREFS
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
encyclopedia(AT)pommard.inria.fr, Jan 25 2000
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|