A052854 Number of forests of ordered trees on n total nodes.

1, 1, 2, 4, 10, 26, 77, 235, 758, 2504, 8483, 29203, 102030, 360442, 1285926, 4625102, 16754302, 61067430, 223803775, 824188993, 3048383517, 11318928477, 42176798315, 157664823501, 591109863049, 2222121888117, 8374151243258, 31630394287364, 119725350703472

Offset: 0

Author

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

Keywords

• easy
• nonn
• nice

Comments

If B is a collection in which there are A000108(n-1) [Catalan numbers] things with n points, a(n) is the number of multisets of B with a total of n points.

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 201 terms from T. D. Noe)
• Steven R. Finch, Errata and Addenda to Mathematical Constants, arXiv:2001.00578 [math.HO], 2020-2022, p. 45.
• P. Flajolet et al., A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics, arXiv:math/0606370 [math.CO], 2006.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 822.
• Florian Luca and Pantelimon Stanica, On the Euler function of the Catalan numbers, Journal of Number Theory, Volume 132, Issue 7, July 2012, Pages 1404-1424.

Crossrefs

Cf. A000108, A052805, A066768.

Cf. A246949.

Programs

Maple

spec := [S,{B=Sequence(C),C=Prod(Z,B),S=Set(C)},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20); # version 1
spec := [ C, {B=Union(Z,Prod(B,B)), C=Set(B)}, unlabeled ]; [seq(combstruct[count](spec, size=n), n=0..40)]; # version 2
# third Maple program:
with(numtheory):
b:= proc(n) option remember; binomial(2*n, n) end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(
      b(d-1), d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Mar 10 2015

Mathematica

max = 27; f[x_] := 1/Product[ (1 - x^k)^CatalanNumber[k - 1], {k, 1, max}]; se = Series[f[x], {x, 0, max}]; CoefficientList[se, x] (* Jean-François Alcover, Oct 05 2011, after g.f. *)

PARI

a(n)=if(n<0,0,polcoeff(1/prod(k=1,n,(1-x^k+x*O(x^n))^((2*k-2)!/k!/(k-1)!)),n))

Formula

Euler transform of Catalan numbers C(n-1) (cf. A000108).

n*a(n) = Sum_{k=1..n} a(n-k)*b(k), b(k) = Sum_{d|k} binomial(2*d-2, d-1) = A066768(k). - Vladeta Jovovic, Jan 17 2002

G.f.: 1/(Product_{k>0} (1-x^k)^C(k-1)) where C() is Catalan numbers.

G.f.: A(z) = Product_{n >= 1} (1-z^n)^(-A000108(n)) = exp(Sum_{k >= 1} C(z^k)/k), where C(z) is the g.f. for the Catalan numbers.

a(n) ~ K 4^(n-1)/sqrt(Pi*n^3), where K ~ 1.71603053492228196404746... (see A246949).

Extensions

Better title from Geoffrey Critzer, Feb 22 2013

Minor edits by Vaclav Kotesovec, May 13 2014