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

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

Author

David Bevan, May 22 2017

Keywords

• nonn

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).

Examples

			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.
		

Links

• Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A000041, A000108, A307496.

Programs

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 *)

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