login
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.
2

%I #19 Sep 15 2024 01:37:15

%S 1,0,3,1,18,15,138,189,1218,2280,11826,27225,123013,325611,1346631,

%T 3919188,15318342,47563620,179405250,582336054,2148831144,7191954822,

%U 26193070008,89559039141,323765075223,1123859351610,4047466156545

%N 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.

%C Column 0 of A120981.

%H Michael De Vlieger, <a href="/A120984/b120984.txt">Table of n, a(n) for n = 0..1750</a>

%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.

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

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

%F 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

%F 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

%e 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.

%p 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);

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

%Y Cf. A120981, A120985.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Jul 21 2006