0,3

T(3n,n)=binom(3n,n)/(2n+1)=A001764(n); T(n,0)=A001006(n) (the Motzkin numbers); T(n,1)= A055219(n-3) (n>=3; most probably); Row sums are the Catalan numbers (A000108).

T(n,k) = number of ordered trees on n edges with k vertices of outdegree at least 3; T(n,k) = number of ordered trees on n edges with k vertices V such that V's rightmost descendant leaf is at distance exactly 3 from V. - David Callan (callan(AT)stat.wisc.edu), Oct 24 2004

T(n,k) is the number of Dyck n-paths containing k UUUDs. For example, T(6,2) = 3 because UUUDUUUDDDDD, UUUDDUUUDDDD, UUUDDDUUUDDD each contains 2 UUUDs. - David Callan (callan(AT)stat.wisc.edu), Nov 04 2004

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

E. Deutsch, A bijection on ordered trees and its consequences, J. Comb. Theory, A, 90, 210-215, 2000.

A. Kuznetsov, I. Pak, A. Postnikov, Trees associated with the Motzkin numbers, J. Comb. Theory, A, 76, 145-147, 1996.

T(n, k)=binomial((n+1), k)*sum((-1)^j*binomial(n+1-k, j)*binomial(2n-3k-3j, n), j=0..floor(n/3)-k)/(n+1). G.f. G=G(t, z) satisfies (t-1)z^3 G^3 + zG^2 - G + 1 = 0.

T(3,1)=1 because the only tree having 3 edges and 1 branch node at an odd level is the tree having the shape of the letter Y.

Triangle begins:

[1],

[1],

[2],

[4, 1],

[9, 5],

[21, 21],

[51, 78, 3],

[127, 274, 28],

[323, 927, 180],

[835, 3061, 954, 12],

[2188, 9933, 4510, 165]

T := (n, k)->binomial((n+1), k)*sum((-1)^j*binomial(n+1-k, j)*binomial(2*n-3*k-3*j, n), j=0..floor(n/3)-k)/(n+1): seq(seq(T(n, k), k=0..floor(n/3)), n=0..18);

Clear[a]; a[n_, k_]/; k>n/3 || k<0 := 0; a[n_, 0]/; 0<=n<=1 := 1; a[n_, 0]/; n>=2 := a[n, 0] = ((2*n + 1)*a[n-1, 0] + 3*(n - 1)*a[n-2, 0])/(n + 2); a[n_, k_]/; 1<=k<=n/3 && n>=2 := a[n, k] = ( (12 - 9*k + 3*n)*a[n-2, k-2] - (12 - 18*k + 3*n)*a[ n-2, k-1] - 9*k*a[ n-2, k] + (4 - 6*k + 4*n)*a[n-1, k-1] + 6*k*a[n-1, k] - (2 - k + n)*a[n, k-1] )/k; Table[a[n, k], {n, 0, 16}, {k, 0, n/3}] (Callan)

Cf. A001764, A001006, A055219.

Topmost entries in each column form A001764=( binomial(3n, n)/(2n+1) )_(n>=0), next to topmost entries form A025174=( binomial(3n+2, n) )_(n>=0), next lower entries are given by ( (n+2)binomial(3n+4, n) )_(n>=0).

Adjacent sequences: A091955 A091956 A091957 this_sequence A091959 A091960 A091961

Sequence in context: A101974 A097607 A132893 this_sequence A116424 A135306 A102405

nonn,tabf

Emeric Deutsch (deutsch(AT)duke.poly.edu), Mar 13 2004