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

Offset: 0

Author

Paul D. Hanna, Jan 29 2010

Keywords

• nonn
• tabl

Examples

			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:
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,2817,2682,4383,1998,4941,3294,3780,2241,4374,2187,2673,1539,1458,729,2187; ...
		

Crossrefs

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

Programs

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

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.