login
Number of ternary trees with n edges and having no vertices of degree 2. A ternary tree is a rooted tree in which each vertex has at most three children and each child of a vertex is designated as its left or middle or right child.
4

%I #18 Mar 23 2024 11:37:48

%S 1,3,9,28,93,333,1272,5085,20925,87735,372879,1602450,6953824,

%T 30438138,134255403,596154495,2662813341,11955684591,53927330037,

%U 244250703252,1110401393067,5065143385647,23176155530394,106344639962973

%N Number of ternary trees with n edges and having no vertices of degree 2. A ternary tree is a rooted tree in which each vertex has at most three children and each child of a vertex is designated as its left or middle or right child.

%C Column 0 of A120982.

%H Vincenzo Librandi, <a href="/A120985/b120985.txt">Table of n, a(n) for n = 0..300</a>

%F a(n) = (1/(n+1)) * Sum_{j..floor(n/3)} 3^(n-3*j) * binomial(n+1,2*j+1) * binomial(n-2*j,j).

%F G.f.=G(z) satisfies G=1+3zG + z^3*G^3.

%F Recurrence: 2*n*(2*n+3)*a(n) = 6*(6*n^2-1)*a(n-1) - 54*(n-1)*(2*n-1)*a(n-2) + 135*(n-2)*(n-1)*a(n-3). - _Vaclav Kotesovec_, Oct 19 2012

%F a(n) ~ (3+3/2^(2/3))^(n+3/2)/(2*sqrt(3*Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 19 2012

%F a(n) = (1/(n+1)) * Sum_{k=0..floor(n/2)} (-3)^k * binomial(n+1,k) * binomial(3*n-3*k+3,n-2*k). - _Seiichi Manyama_, Mar 23 2024

%e a(1)=3 because we have (Q,L), (Q,M) and (Q,R), where Q denotes the root and L (M,R) denotes a left (middle, right) child of Q.

%p a:=n->sum(3^(n-3*j)*binomial(n+1,2*j+1)*binomial(n-2*j,j),j=0..n/2)/(n+1): seq(a(n),n=0..27);

%t Table[1/(n+1)*Sum[3^(n-3*j)*Binomial[n+1,2*j+1]*Binomial[n-2*j,j],{j,0,n/2}],{n,0,20}] (* _Vaclav Kotesovec_, Oct 19 2012 *)

%Y Cf. A120982.

%K nonn

%O 0,2

%A _Emeric Deutsch_, Jul 21 2006