OFFSET
0,3
COMMENTS
n divides a(n) iff the binary representation of n ends with an even number of zeros (i.e., n is in A003159).
From Petros Hadjicostas, Jun 03 2020: (Start)
The sequence appears twice on p. 39 of Salaam (2008). For n >= 1, a(n-1) counts 2-sets of leaves in "0,1,2" Motzkin rooted trees with n edges. It also counts 2-sets of leaves in non-redundant 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. Non-redundant trees are ordered trees where no vertex has out-degree equal to 1 (and they are sometimes known as Riordan trees). They are counted by the Riordan numbers A005043.
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 non-redundant trees, the situation is more complicated and no g.f. is given for a general r >= 5. (End)
LINKS
Harvey P. Dale, Table of n, a(n) for n = 0..1000
Lifoma Salaam, Combinatorial statistics on phylogenetic trees, Ph.D. Dissertation, Howard University, Washington D.C., 2008. [See Theorem 39 (p. 25) for "0,1,2" trees and p. 27 for non-redundant trees.]
FORMULA
a(n) is asymptotic to c*sqrt(n)*3^n where c = 0.2443012(5)....
G.f.: x/(1 - 2*x - 3*x^2)^(3/2). - Vladeta Jovovic, Oct 24 2007
a(n) = 4^(n-1)*JacobiP[n-1,-n-1/2,-n-1/2,-1/2]. - Peter Luschny, May 13 2016
a(n) ~ sqrt(3*n/Pi)*3^n/4. - Vaclav Kotesovec, May 13 2016
a(n) = binomial(n+1,2)*A001006(n-1). - Kassie Archer, Apr 14 2022
EXAMPLE
From Petros Hadjicostas, Jun 03 2020: (Start)
With n = 3 edges, we list below the a(3-1) = 3 two-sets of leaves among all A001006(3) = 4 Motzkin trees:
A A
| |
| |
B B
| / \
| / \
C C D
| {C, D}
|
D
No 2-sets of leaves
A A
/ \ / \
/ \ / \
B C B C
| |
| |
D D
{C, D} {B, D}
With n = 3 edges, there is only A005043(3) = 1 non-redundant tree and a(3-1) = 3 two-sets of leaves:
A
/|\
/ | \
B C D
{B, C}, {B, D}, {C, D}
With n = 4 edges there are A005043(4) = 3 non-redundant trees and a(4-1) = 12 two-sets of leaves:
A A A
/ / \ \ / \ / \
/ / \ \ / \ / \
B C D E B C B C
{B, C}, {B, D}, {B, E}, / \ / \
{C, D}, {C, E}, {D, E} / \ / \
D E D E
{D, E}, {D, C}, {E, C} {B, D}, {B, E}, {D, E}
(End)
MAPLE
seq(add(k*binomial(n, k)*binomial(n-k, k)/2, k=0..n), n=1..26); # Zerinvary Lajos, Oct 23 2007
MATHEMATICA
Table[4^(n-1)*JacobiP[n-1, -n-1/2, -n-1/2, -1/2], {n, 0, 25}] (* Peter Luschny, May 13 2016 *)
nxt[{n_, a_, b_}]:={n+1, b, (b(2n+1)+3a(n+1))/n}; NestList[nxt, {1, 0, 1}, 30][[;; , 2]] (* Harvey P. Dale, Mar 31 2024 *)
PROG
(PARI) a(n) = if(n<2, if(n, 1, 0), 1/(n-1)*((2*n-1)*a(n-1)+3*n*a(n-2)))
CROSSREFS
KEYWORD
nonn
AUTHOR
Benoit Cloitre, Feb 27 2005
STATUS
approved