A171793 - OEIS

A171793

Triangle read by rows: T(n,k) is the number of ternary trees with n edges and path length k; 0<=k<=n(n-1)/2.

1, 1, 0, 3, 0, 0, 3, 9, 0, 0, 0, 1, 18, 9, 27, 0, 0, 0, 0, 0, 9, 45, 57, 54, 27, 81, 0, 0, 0, 0, 0, 0, 0, 36, 87, 270, 81, 297, 171, 162, 81, 243, 0, 0, 0, 0, 0, 0, 0, 0, 0, 84, 261, 567, 756, 936, 585, 972, 729, 891, 513, 486, 243, 729, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 126, 774, 1080

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,4

LINKS

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

FORMULA

G.f. satisfies: A(x,q) = 1 + x*A(q*x,q)^3.

Row sums equal A001764, which enumerates ternary trees and has g.f.: G(x) = 1 + x*G(x)^3.

Column sums equal A132331(k), which is the number of ternary trees of path length k.

EXAMPLE

G.f.: A(x,q) = 1 + x + (3*q)*x^2 + (3*q^2 + 9*q^3)*x^3 + (q^3 + 18*q^4 + 9*q^5 + 27*q^6)*x^4 +...

A(x,q)^3 = 1 + 3*x + (3 + 9*q)*x^2 + (1 + 18*q + 9*q^2 + 27*q^3)*x^3 +...

Triangle begins:

0,3;

0,0,3,9;

0,0,0,1,18,9,27;

0,0,0,0,0,9,45,57,54,27,81;

0,0,0,0,0,0,0,36,87,270,81,297,171,162,81,243;

0,0,0,0,0,0,0,0,0,84,261,567,756,936,585,972,729,891,513,486,243,729;

0,0,0,0,0,0,0,0,0,0,0,126,774,1080,2817,2682,4383,1998,4941,3294,3780,2241,4374,2187,2673,1539,1458,729,2187; ...

PROG

(PARI) {T(n, k)=local(A=1+x); for(i=1, n, A=1+x*subst(A, x, q*x+x*O(x^n))^3); polcoeff(polcoeff(A, n, x)+O(q^(n*(n-1)/2+1)), k, q)}

CROSSREFS

Cf. A001764 (row sums), A132331 (column sums), A138157 (variant).

Sequence in context: A200517 A363035 A151665 * A079209 A079201 A279368

Adjacent sequences: A171790 A171791 A171792 * A171794 A171795 A171796

KEYWORD

nonn,tabl

AUTHOR

Paul D. Hanna, Jan 29 2010

STATUS

approved