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, 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

Offset

0,4

Comments

Previous name was: "A simple grammar".

a(n) is the number of unlabelled 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

Alois P. Heinz, Table of n, a(n) for n = 0..1000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 792

Formula

G.f.: Product_{k >= 1} (1+x^k)^A000081(k). - Vladeta Jovovic, May 14 2005

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):
seq(a(n), n=0..30);  # Alois P. Heinz, Jul 08 2015

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

Cf. A000081.

Sequence in context: A209450 A291013 A017924 * A033192 A174297 A005043

Adjacent sequences: A052824 A052825 A052826 * A052828 A052829 A052830

Keyword

easy,nonn

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Extensions

More terms from Paul D. Hanna, Jul 13 2006

New name using a comment of Geoffrey Critzer by Peter Luschny, Dec 06 2020

Status

approved