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
Keywords
Examples
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.
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.
Programs
-
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 *)
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
Comments