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.

1, 3, 9, 3, 27, 27, 1, 81, 162, 30, 243, 810, 360, 15, 729, 3645, 2970, 405, 3, 2187, 15309, 19845, 5670, 252, 6561, 61236, 115668, 56700, 6426, 84, 19683, 236196, 612360, 459270, 98658, 4536, 12, 59049, 885735, 3018060, 3214890, 1122660

Offset: 0

Author

Emeric Deutsch, Jul 21 2006

Keywords

• nonn
• tabf

Comments

Row n has n + 1 - ceiling(n/3) terms.

Row sums yield A001764.

T(n,1) = 3^n = A000244(n).

Sum_{k>=1} k*T(n,k) = binomial(3n,n) = A005809(n).

Examples

			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.
Triangle starts:
    1;
    3;
    9,   3;
   27,  27,   1;
   81, 162,  30;
  243, 810, 360,  15;
		

Crossrefs

Cf. A001764, A000244, A005809, A120981, A120982, A120983.

Programs

Maple

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

Formula

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).

G.f. = G = G(t,z) satisfies G = (1+z(G-1+t))^3.