A120984 Number of ternary trees with n edges and having no vertices of degree 1. 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, 0, 3, 1, 18, 15, 138, 189, 1218, 2280, 11826, 27225, 123013, 325611, 1346631, 3919188, 15318342, 47563620, 179405250, 582336054, 2148831144, 7191954822, 26193070008, 89559039141, 323765075223, 1123859351610, 4047466156545

Offset

0,3

Comments

Column 0 of A120981.

Links

Michael De Vlieger, Table of n, a(n) for n = 0..1750

Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.

Formula

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

G.f.: G(z) satisfies G=1+3z^2*G^2+z^3*G^3.

D-finite with recurrence 2*(2*n+3)*(n+1)*a(n) +3*(3*n+2)*(n-1)*a(n-1) -18*(3*n+1)*(n-1)*a(n-2) -135*(n-1)*(n-2)*a(n-3)=0. - R. J. Mathar, Jul 26 2022

a(n) = (1/(n+1)) * Sum_{k=0..n} (-3)^k * binomial(n+1,k) * binomial(3*n-3*k+3,n-k). - Seiichi Manyama, Mar 23 2024

Example

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

Maple

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

Mathematica

Array[Sum[3^(3 j - #)*Binomial[# + 1, j]*Binomial[j, # - 2 j], {j, 0, # + 1}]/(# + 1) &, 27, 0] (* Michael De Vlieger, Jul 02 2021 *)

Crossrefs

Cf. A120981, A120985.

Sequence in context: A051238 A283150 A307064 * A294792 A290317 A016480

Adjacent sequences: A120981 A120982 A120983 * A120985 A120986 A120987

Keyword

nonn

Author

Emeric Deutsch, Jul 21 2006

Status

approved