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,2

Comments

Column 0 of A120982.

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..300

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

Example

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.

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

Crossrefs

Cf. A120982.

Sequence in context: A238978 A081914 A361763 * A014323 A000752 A047027

Adjacent sequences: A120982 A120983 A120984 * A120986 A120987 A120988

Keyword

nonn

Author

Emeric Deutsch, Jul 21 2006

Status

approved