A120985 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.
1, 3, 9, 28, 93, 333, 1272, 5085, 20925, 87735, 372879, 1602450, 6953824, 30438138, 134255403, 596154495, 2662813341, 11955684591, 53927330037, 244250703252, 1110401393067, 5065143385647, 23176155530394, 106344639962973
Offset: 0
Keywords
Examples
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.
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..300
Crossrefs
Cf. A120982.
Programs
-
Maple
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);
-
Mathematica
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 *)
Formula
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).
G.f.=G(z) satisfies G=1+3zG + z^3*G^3.
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
a(n) ~ (3+3/2^(2/3))^(n+3/2)/(2*sqrt(3*Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 19 2012
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
Comments