|
%I #59 Mar 31 2024 15:56:57
%S 0,1,3,12,40,135,441,1428,4572,14535,45925,144408,452244,1411501,
%T 4392675,13636080,42237792,130580451,403009209,1241912580,3821849640,
%U 11746816389,36064532427,110610649548,338928124500,1037636534025
%N a(0) = 0, a(1) = 1, and a(n) = ((2*n - 1)*a(n-1) + 3*n*a(n-2))/(n - 1) for n >= 2.
%C n divides a(n) iff the binary representation of n ends with an even number of zeros (i.e., n is in A003159).
%C From _Petros Hadjicostas_, Jun 03 2020: (Start)
%C 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.
%C "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.
%C 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)
%H Harvey P. Dale, <a href="/A102839/b102839.txt">Table of n, a(n) for n = 0..1000</a>
%H Lifoma Salaam, <a href="https://search.proquest.com/docview/193997569">Combinatorial statistics on phylogenetic trees</a>, 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.]
%F a(n) is asymptotic to c*sqrt(n)*3^n where c = 0.2443012(5)....
%F G.f.: x/(1 - 2*x - 3*x^2)^(3/2). - _Vladeta Jovovic_, Oct 24 2007
%F a(n) = 4^(n-1)*JacobiP[n-1,-n-1/2,-n-1/2,-1/2]. - _Peter Luschny_, May 13 2016
%F a(n) ~ sqrt(3*n/Pi)*3^n/4. - _Vaclav Kotesovec_, May 13 2016
%F a(n) = binomial(n+1,2)*A001006(n-1). - _Kassie Archer_, Apr 14 2022
%e From _Petros Hadjicostas_, Jun 03 2020: (Start)
%e With n = 3 edges, we list below the a(3-1) = 3 two-sets of leaves among all A001006(3) = 4 Motzkin trees:
%e A A
%e | |
%e | |
%e B B
%e | / \
%e | / \
%e C C D
%e | {C, D}
%e |
%e D
%e No 2-sets of leaves
%e A A
%e / \ / \
%e / \ / \
%e B C B C
%e | |
%e | |
%e D D
%e {C, D} {B, D}
%e With n = 3 edges, there is only A005043(3) = 1 non-redundant tree and a(3-1) = 3 two-sets of leaves:
%e A
%e /|\
%e / | \
%e B C D
%e {B, C}, {B, D}, {C, D}
%e With n = 4 edges there are A005043(4) = 3 non-redundant trees and a(4-1) = 12 two-sets of leaves:
%e A A A
%e / / \ \ / \ / \
%e / / \ \ / \ / \
%e B C D E B C B C
%e {B, C}, {B, D}, {B, E}, / \ / \
%e {C, D}, {C, E}, {D, E} / \ / \
%e D E D E
%e {D, E}, {D, C}, {E, C} {B, D}, {B, E}, {D, E}
%e (End)
%p seq(add(k*binomial(n, k)*binomial(n-k, k)/2, k=0..n), n=1..26); # _Zerinvary Lajos_, Oct 23 2007
%t Table[4^(n-1)*JacobiP[n-1,-n-1/2,-n-1/2,-1/2], {n,0,25}] (* _Peter Luschny_, May 13 2016 *)
%t 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 *)
%o (PARI) a(n) = if(n<2,if(n,1,0),1/(n-1)*((2*n-1)*a(n-1)+3*n*a(n-2)))
%Y Cf. A000108, A001006, A005043, A002426.
%K nonn
%O 0,3
%A _Benoit Cloitre_, Feb 27 2005
|
