OFFSET
0,2
COMMENTS
From Petros Hadjicostas, Jun 03 2020: (Start)
For n >= 4, 2*a(n-4) counts 3-sets of leaves in "0,1,2" Motzkin rooted trees with n edges. "0,1,2" trees are rooted trees where each vertex has out-degree zero, one, or two. They are counted by the Motzkin numbers A001006.
For "0,1,2" trees, Salaam (2008) proved that the g.f. of the number of r-sets of leaves is A000108(r-1) * z^(2*r-2) * T(z)^(2*r-1), where T(z) = 1/sqrt(1 - 2*z - 3*z^2) is the g.f. of the central trinomial numbers A002426.
For r = 2, we get a shifted version of A102839. For r = 3, we get twice of a shifted version of the current sequence. (End)
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 6.
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008; see Theorem 39 (p. 25).
J. Y. X. Yang, M. X. X. Zhong, and R. D. P. Zhou, On the Enumeration of (s, s+ 1, s+2)-Core Partitions, arXiv preprint arXiv:1406.2583 [math.CO], 2014. See Theorem 4.2.
FORMULA
a(n) ~ 3^(n+3/2) * n^(3/2) / (8*sqrt(Pi)). - Vaclav Kotesovec, Jul 31 2014
a(n) = (2+3/n)*a(n-1) + (3+9/n)*a(n-2) for n >= 2. - Robert Israel, Aug 01 2014
a(n) = (binomial(n+4,2)/6) * Sum_{k=0..floor(n/2)} binomial(n+2,n-2*k) * binomial(2*k+2,k). - Seiichi Manyama, Jul 10 2024
EXAMPLE
From Petros Hadjicostas, Jun 03 2020: (Start)
Out of the A001006(4) = 9 Motzkin trees with n = 4 edges, only the following 2*a(4-4) = 2 have 3-sets of leaves:
A A
/ \ / \
/ \ / \
B C B C
/ \ / \
/ \ / \
D E D E
{C, D, E} {B, D, E}
(End)
MAPLE
A[0]:= 1: A[1]:= 5:
for n from 2 to 100 do
A[n]:= (2+3/n)*A[n-1] + (3+9/n)*A[n-2]
od:
seq(A[n], n=0..100); # Robert Israel, Aug 01 2014
MATHEMATICA
CoefficientList[Series[1/(1 - 2 x - 3 x^2)^(5/2), {x, 0, 30}], x] (* Vincenzo Librandi, Aug 01 2014 *)
PROG
(PARI) x='x+O('x^50); Vec(1/(1-2*x-3*x^2)^(5/2)) \\ G. C. Greubel, Apr 06 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Jul 30 2014
STATUS
approved