A091958 Triangle read by rows: T(n,k)=number of ordered trees with n edges and k branch nodes at odd height.

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, 5798, 31824, 19734, 1430, 15511, 100972, 81684, 9790, 55, 41835, 317942, 324246, 57876, 1001, 113634, 995088, 1245762, 309036, 10920

Offset: 0

Author

Emeric Deutsch, Mar 13 2004

Keywords

• nonn
• tabf

Comments

T(3n,n) = binomial(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, 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, Nov 04 2004

Examples

			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;
		

Links

• Alois P. Heinz, Rows n = 0..250, flattened
• 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.
• A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Crossrefs

Cf. A001764, A001006, A055219, A243752.

Topmost entries in each column form A001764=( binomial(3n, n)/(2n+1) )A025174=(%20binomial(3n+2,%20n)%20)">(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).

Programs

Maple

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);
# second Maple program:
b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
     `if`(x=0, 1, expand(b(x-1, y+1, [2, 3, 4, 4][t])
      +b(x-1, y-1, [1, 1, 1, 1][t])*`if`(t=4, z, 1))))
    end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
seq(T(n), n=0..15);  # Alois P. Heinz, Jun 10 2014

Mathematica

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)
T[n_, k_] := (2*n-3*k)!*HypergeometricPFQ[{k-n-1, k-n/3, 1/3+k-n/3, 2/3+k-n/3}, {k-2*n/3, 1/3+k-2*n/3, 2/3+k-2*n/3}, 1]/(k!*(n-k+1)!*(n-3*k)!); Table[T[n, k], {n, 0, 15}, {k, 0, n/3}] // Flatten (* Jean-François Alcover, Mar 31 2015 *)

Formula

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.