login
a(n) is the number of unlabeled forests of rooted trees with n nodes such that no two trees are identical.
1

%I #43 Jul 14 2024 17:31:57

%S 1,1,1,3,6,15,36,90,225,578,1492,3901,10278,27313,73042,196585,531847,

%T 1445991,3948282,10823524,29776129,82183115,227501127,631494797,

%U 1757297207,4901491697,13700742034,38373104938,107675540083,302664162746,852138516321,2402817160804

%N a(n) is the number of unlabeled forests of rooted trees with n nodes such that no two trees are identical.

%C Previous name was: "A simple grammar".

%C 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.

%H Alois P. Heinz, <a href="/A052827/b052827.txt">Table of n, a(n) for n = 0..1000</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=792">Encyclopedia of Combinatorial Structures 792</a>

%F G.f.: Product_{k >= 1} (1+x^k)^A000081(k). - _Vladeta Jovovic_, May 14 2005

%F 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

%e A(x) = 1 + x + x^2 + 3*x^3 + 6*x^4 + 15*x^5 + 36*x^6 + 90*x^7 +...

%p spec := [S,{B=Set(C),C=Prod(B,Z),S=PowerSet(C)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

%p # second Maple program:

%p with(numtheory):

%p b:= proc(n) option remember; `if`(n<=1, n, (add(add(

%p d*b(d), d=divisors(j))*b(n-j), j=1..n-1))/(n-1))

%p end:

%p g:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,

%p add(binomial(b(i), j)*g(n-i*j, i-1), j=0..n/i)))

%p end:

%p a:= n-> g(n$2):

%p seq(a(n), n=0..31); # _Alois P. Heinz_, Jul 08 2015

%t 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_ *)

%o (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

%Y Cf. A000081.

%K easy,nonn

%O 0,4

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

%E More terms from _Paul D. Hanna_, Jul 13 2006

%E New name using a comment of _Geoffrey Critzer_ by _Peter Luschny_, Dec 06 2020