A120981 Triangle read by rows: T(n,k) is the number of ternary trees with n edges and having k vertices of outdegree 1 (n >= 0, k >= 0).

1, 0, 3, 3, 0, 9, 1, 27, 0, 27, 18, 12, 162, 0, 81, 15, 270, 90, 810, 0, 243, 138, 270, 2430, 540, 3645, 0, 729, 189, 2898, 2835, 17010, 2835, 15309, 0, 2187, 1218, 4536, 34776, 22680, 102060, 13608, 61236, 0, 6561, 2280, 32886, 61236, 312984, 153090, 551124

Offset

0,3

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

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.

Formula

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

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

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

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

Example

T(2,0)=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;
   0,   3;
   3,   0,   9;
   1,  27,   0,  27;
  18,  12, 162,   0, 81;
  15, 270,  90, 810,  0, 243;

Maple

T:=proc(n, k) if k<=n then (1/(n+1))*binomial(n+1, k)*sum(3^(3*j-n+2*k)*binomial(n+1-k, j)*binomial(j, n-k-2*j), j=0..n+1-k) else 0 fi end: for n from 0 to 10 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Mathematica

T[n_, k_] := (1/(n+1))*Binomial[n+1, k]*Sum[3^(2k - n + 3j)*Binomial[n + 1 - k, j]*Binomial[j, n - k - 2j], {j, 0, n - k + 1}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 02 2018 *)

Prog

(PARI) T(n, k) = binomial(n+1, k)*sum(j=0, n+1-k, 3^(2*k-n+3*j)*binomial(n+1-k, j)*binomial(j, n-k-2*j))/(n+1); \\ Andrew Howroyd, Nov 06 2017
(Python)
from sympy import binomial
def T(n, k): return binomial(n + 1, k)*sum([3**(2*k - n + 3*j)*binomial(n + 1 - k, j)*binomial(j, n - k - 2*j) for j in range(n + 2 - k)])//(n + 1)
for n in range(21): print([T(n, k) for k in range(n + 1)]) # Indranil Ghosh, Nov 07 2017

Crossrefs

Diagonals include A129530, A036216.

Cf. A001764 (row sums), A004319, A120429, A120982, A120983, A120984.

Sequence in context: A169670 A372004 A341748 * A298850 A262292 A100543

Adjacent sequences: A120978 A120979 A120980 * A120982 A120983 A120984

Keyword

nonn,tabl

Author

Emeric Deutsch, Jul 21 2006

Status

approved