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,2

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

Links

Table of n, a(n) for n=0..41.

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.

Example

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;

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

Crossrefs

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

Sequence in context: A010259 A255583 A339882 * A101431 A120982 A293634

Adjacent sequences: A120426 A120427 A120428 * A120430 A120431 A120432

Keyword

nonn,tabf

Author

Emeric Deutsch, Jul 21 2006

Status

approved