login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A120983 Triangle read by rows: T(n,k) is the number of ternary trees with n edges and having k vertices of outdegree 3 (n >= 0, k >= 0). 3
1, 3, 12, 54, 1, 261, 12, 1323, 105, 6939, 810, 3, 37341, 5859, 63, 205011, 40824, 840, 1143801, 277830, 9072, 12, 6466230, 1861380, 86670, 360, 36960300, 12335895, 764478, 6435, 213243435, 81120204, 6377778, 89100, 55, 1240219269, 530408736 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

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.

LINKS

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

FORMULA

T(n,k) = (1/(n+1))*binomial(n+1,k)*Sum_{j=0..n+1-k} 3^j*binomial(n+1-k, j)*binomial(j, n-3k-j).

G.f.: G = G(t,z) satisfies G = 1 + 3zG + 3z^2*G^2 + tz^3*G^3.

Row n has 1+floor(n/3) terms.

Row sums yield A001764.

T(n,0) = A107264(n).

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

EXAMPLE

T(3,1)=1 because we have (Q,L,M,R), where Q denotes the root and L (M,R) denotes a left (middle, right) child of Q.

Triangle starts:

     1;

     3;

    12;

    54,   1;

   261,  12;

  1323, 105;

  6939, 810, 3;

MAPLE

T:=(n, k)->(1/(n+1))*binomial(n+1, k)*sum(3^j*binomial(n+1-k, j)*binomial(j, n-3*k-j), j=0..n+1-k): for n from 0 to 14 do seq(T(n, k), k=0..floor(n/3)) od; # yields sequence in triangular form

CROSSREFS

Cf. A001764, A107264, A120429, A120981, A120982, A004321.

Sequence in context: A060460 A306525 A293131 * A124810 A329056 A191577

Adjacent sequences:  A120980 A120981 A120982 * A120984 A120985 A120986

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Jul 21 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 6 21:41 EDT 2020. Contains 335483 sequences. (Running on oeis4.)