login
Number of forests of ordered trees on n total nodes.
5

%I #70 Jan 07 2024 12:10:24

%S 1,1,2,4,10,26,77,235,758,2504,8483,29203,102030,360442,1285926,

%T 4625102,16754302,61067430,223803775,824188993,3048383517,11318928477,

%U 42176798315,157664823501,591109863049,2222121888117,8374151243258,31630394287364,119725350703472

%N Number of forests of ordered trees on n total nodes.

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

%H Alois P. Heinz, <a href="/A052854/b052854.txt">Table of n, a(n) for n = 0..1000</a> (first 201 terms from T. D. Noe)

%H Steven R. Finch, <a href="http://arxiv.org/abs/2001.00578">Errata and Addenda to Mathematical Constants</a>, arXiv:2001.00578 [math.HO], 2020-2022, p. 45.

%H P. Flajolet et al., <a href="http://arXiv.org/abs/math.CO/0606370">A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics</a>, arXiv:math/0606370 [math.CO], 2006.

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

%H Florian Luca and Pantelimon Stanica, <a href="https://doi.org/10.1016/j.jnt.2012.02.002">On the Euler function of the Catalan numbers</a>, Journal of Number Theory, Volume 132, Issue 7, July 2012, Pages 1404-1424.

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

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

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

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

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

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

%p spec := [ C, {B=Union(Z,Prod(B,B)), C=Set(B)}, unlabeled ]; [seq(combstruct[count](spec, size=n), n=0..40)]; # version 2

%p # third Maple program:

%p with(numtheory):

%p b:= proc(n) option remember; binomial(2*n, n) end:

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

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

%p end:

%p seq(a(n), n=0..35); # _Alois P. Heinz_, Mar 10 2015

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

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

%Y Cf. A000108, A052805, A066768.

%Y Cf. A246949.

%K easy,nonn,nice

%O 0,3

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

%E Better title from _Geoffrey Critzer_, Feb 22 2013

%E Minor edits by _Vaclav Kotesovec_, May 13 2014