login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 21 04:10 EDT 2021. Contains 345354 sequences. (Running on oeis4.)