login
A286955
n-vertex sequences of plane forests with nondecreasing numbers of trees.
6
1, 1, 3, 9, 29, 96, 326, 1127, 3952, 14019, 50208, 181275, 659039, 2410433, 8862750, 32739168, 121443136, 452167865, 1689237104, 6330103627, 23787215202, 89616350271, 338417312294, 1280739676563, 4856711761475, 18451630811041, 70223495698892, 267691953822783
OFFSET
0,3
COMMENTS
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).
LINKS
FORMULA
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.
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
EXAMPLE
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.
MATHEMATICA
m = 20; CoefficientList[Series[Product[1/(1-((1-Sqrt[1-4x])/2)^k), {k, m}], {x, 0, m}], x]
nmax = 30; CoefficientList[Series[1/QPochhammer[(1 - Sqrt[1 - 4*x])/2], {x, 0, nmax}], x] (* Vaclav Kotesovec, Mar 10 2020 *)
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 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
David Bevan, May 22 2017
STATUS
approved