A286955 - OEIS

%I #42 Aug 01 2022 08:36:16

%S 1,1,3,9,29,96,326,1127,3952,14019,50208,181275,659039,2410433,

%T 8862750,32739168,121443136,452167865,1689237104,6330103627,

%U 23787215202,89616350271,338417312294,1280739676563,4856711761475,18451630811041,70223495698892,267691953822783

%N n-vertex sequences of plane forests with nondecreasing numbers of trees.

%C Enumerates Part[Cat], the substitution of Cat for atoms of Part, where Part is the set of integer partitions (A000041), and Cat is any set counted by the 1-based Catalan numbers (A000108 shifted).

%H Vaclav Kotesovec, <a href="/A286955/b286955.txt">Table of n, a(n) for n = 0..1000</a>

%F G.f.: Product_{k>0} 1/(1 - ((1 - sqrt(1 - 4*x))/2)^k), the composition of the g.f. for A000041 with x times the g.f. for A000108.

%F a(n) ~ c * 4^n / n^(3/2), where c = 1/sqrt(Pi) * Sum_{k>=0} k*A000041(k)/2^(k+1) = 2.680434829690402658212615372294526133126515771886321123341424399596963885434... - _Vaclav Kotesovec_, Jun 02 2018, extended Aug 01 2022

%e a(3) = 9, consisting of (1,1,1), (1,2), (2,1), (3a), (3b), (1)(1,1), (1)(2), (2)(1), and (1)(1)(1), where 1 is the one-vertex tree, 2 is the two-vertex tree, 3a and 3b are the two three-vertex trees, and parentheses record the partitioning into forests. (1,1)(1) is excluded because the numbers of trees per forest decreases.

%t m = 20; CoefficientList[Series[Product[1/(1-((1-Sqrt[1-4x])/2)^k),{k,m}],{x,0,m}],x]

%t nmax = 30; CoefficientList[Series[1/QPochhammer[(1 - Sqrt[1 - 4*x])/2], {x, 0, nmax}], x] (* _Vaclav Kotesovec_, Mar 10 2020 *)

%t Join[{1}, Table[Sum[(k/(2*n - k))*Binomial[2*n - k, n - k]*PartitionsP[k], {k, 0, n}], {n, 1, 30}]] (* _Vaclav Kotesovec_, Jul 31 2022 *)

%Y Cf. A000041, A000108, A307496.

%K nonn

%O 0,3

%A _David Bevan_, May 22 2017