|
%I #7 Jul 21 2017 13:38:20
%S 1,3,9,3,27,27,1,81,162,30,243,810,360,15,729,3645,2970,405,3,2187,
%T 15309,19845,5670,252,6561,61236,115668,56700,6426,84,19683,236196,
%U 612360,459270,98658,4536,12,59049,885735,3018060,3214890,1122660
%N 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 Row n has n + 1 - ceiling(n/3) terms.
%C Row sums yield A001764.
%C T(n,1) = 3^n = A000244(n).
%C Sum_{k>=1} k*T(n,k) = binomial(3n,n) = A005809(n).
%F 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 G.f. = G = G(t,z) satisfies G = (1+z(G-1+t))^3.
%e 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 Triangle starts:
%e 1;
%e 3;
%e 9, 3;
%e 27, 27, 1;
%e 81, 162, 30;
%e 243, 810, 360, 15;
%p 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 Cf. A001764, A000244, A005809, A120981, A120982, A120983.
%K nonn,tabf
%O 0,2
%A _Emeric Deutsch_, Jul 21 2006
|
