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

%I #20 Jul 02 2021 16:46:45

%S 1,0,3,3,0,9,1,27,0,27,18,12,162,0,81,15,270,90,810,0,243,138,270,

%T 2430,540,3645,0,729,189,2898,2835,17010,2835,15309,0,2187,1218,4536,

%U 34776,22680,102060,13608,61236,0,6561,2280,32886,61236,312984,153090,551124

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

%C 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.

%H Andrew Howroyd, <a href="/A120981/b120981.txt">Table of n, a(n) for n = 0..1274</a>

%H Paul Barry, <a href="https://arxiv.org/abs/2104.01644">Centered polygon numbers, heptagons and nonagons, and the Robbins numbers</a>, arXiv:2104.01644 [math.CO], 2021.

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

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

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

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

%e 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.

%e Triangle starts:

%e 1;

%e 0, 3;

%e 3, 0, 9;

%e 1, 27, 0, 27;

%e 18, 12, 162, 0, 81;

%e 15, 270, 90, 810, 0, 243;

%p 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

%t 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}];

%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jul 02 2018 *)

%o (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

%o (Python)

%o from sympy import binomial

%o 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)

%o for n in range(21): print([T(n, k) for k in range(n + 1)]) # _Indranil Ghosh_, Nov 07 2017

%Y Diagonals include A129530, A036216.

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

%K nonn,tabl

%O 0,3

%A _Emeric Deutsch_, Jul 21 2006