cp's OEIS Frontend

A120429 Triangle read by rows: T(n,k) is the number of ternary trees with n edges and having k leaves (i.e., vertices of degree 0; n>=0, k>=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.

%I A120429 #7 Jul 21 2017 13:38:20
%S A120429 1,3,9,3,27,27,1,81,162,30,243,810,360,15,729,3645,2970,405,3,2187,
%T A120429 15309,19845,5670,252,6561,61236,115668,56700,6426,84,19683,236196,
%U A120429 612360,459270,98658,4536,12,59049,885735,3018060,3214890,1122660
%N A120429 Triangle read by rows: T(n,k) is the number of ternary trees with n edges and having k leaves (i.e., vertices of degree 0; n>=0, k>=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 A120429 Row n has n + 1 - ceiling(n/3) terms.
%C A120429 Row sums yield A001764.
%C A120429 T(n,1) = 3^n = A000244(n).
%C A120429 Sum_{k>=1} k*T(n,k) = binomial(3n,n) = A005809(n).
%F A120429 T(n,k) = (1/(n+1))*binomial(n+1,k)*Sum_{j=0..n+1-k}3^(n-2k+j+2)*binomial(n+1-k,j)*binomial(j,k-1-j).
%F A120429 G.f. = G = G(t,z) satisfies G = (1+z(G-1+t))^3.
%e A120429 T(2,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.
%e A120429 Triangle starts:
%e A120429     1;
%e A120429     3;
%e A120429     9,   3;
%e A120429    27,  27,   1;
%e A120429    81, 162,  30;
%e A120429   243, 810, 360,  15;
%p A120429 T:=proc(n,k) if k<=n+1-ceil(n/3) then (1/(n+1))*binomial(n+1,k)*sum(3^(n+j-2*k+2)*binomial(n+1-k,j)*binomial(j,k-1-j),j=0..n+1-k) else 0 fi end: 1; for n from 1 to 11 do seq(T(n,k),k=1..n+1-ceil(n/3)) od; # yields sequence in triangular form
%Y A120429 Cf. A001764, A000244, A005809, A120981, A120982, A120983.
%K A120429 nonn,tabf
%O A120429 0,2
%A A120429 _Emeric Deutsch_, Jul 21 2006