|
| |
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
