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

0, 1, 3, 12, 40, 135, 441, 1428, 4572, 14535, 45925, 144408, 452244, 1411501, 4392675, 13636080, 42237792, 130580451, 403009209, 1241912580, 3821849640, 11746816389, 36064532427, 110610649548, 338928124500, 1037636534025

Offset: 0

Author

Benoit Cloitre, Feb 27 2005

Keywords

• nonn

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)

Examples

			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)
		

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

Crossrefs

Cf. A000108, A001006, A005043, A002426.

Programs

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

PARI

a(n) = if(n<2,if(n,1,0),1/(n-1)*((2*n-1)*a(n-1)+3*n*a(n-2)))

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