A126181 Triangle read by rows, T(n,k) = C(n,k)*Catalan(n-k+1), n >= 0, 0 <= k <= n.

1, 2, 1, 5, 4, 1, 14, 15, 6, 1, 42, 56, 30, 8, 1, 132, 210, 140, 50, 10, 1, 429, 792, 630, 280, 75, 12, 1, 1430, 3003, 2772, 1470, 490, 105, 14, 1, 4862, 11440, 12012, 7392, 2940, 784, 140, 16, 1, 16796, 43758, 51480, 36036, 16632, 5292, 1176, 180, 18, 1, 58786

Offset: 0

Author

Emeric Deutsch, Dec 19 2006, Mar 30 2007

Keywords

• nonn
• tabl

Comments

T(n,k) is the number of hex trees with n edges and k nodes having median children (i.e., k vertical edges; 0 <= k <= n). A hex tree is a rooted tree where each vertex has 0, 1, or 2 children and, when only one child is present, it is either a left child, or a median child, or a right child (name due to an obvious bijection with certain tree-like polyhexes; see the Harary-Read paper).

Also, with offset 1, triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k left steps (n >= 1; 0 <= k <= n-1). A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of its steps. For example, T(4,2)=6 because we have UDUUUDLL, UUUUDLLD, UUDUUDLL, UUUUDLDL, UUUDUDLL and UUUUDDLL.

Also, with offset 1, number of skew Dyck paths of semilength and having k UDU's. Example: T(3,1)=4 because we have (UDU)UDD, (UDU)UDL, U(UDU)DD and U(UDU)DL (the UDU's are shown between parentheses).

Examples

			Triangle starts:
   1;
   2,  1;
   5,  4,  1;
  14, 15,  6,  1;
  42, 56, 30,  8,  1;
		

Links

• F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.

Crossrefs

Mirror image of A108198.

Cf. A002212, A000108, A026376.

Programs

Maple

c:=n->binomial(2*n,n)/(n+1): T:=proc(n,k) if k<=n then binomial(n,k)*c(n-k+1) else 0 fi end: for n from 0 to 10 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form
# Second implementation:
h := n -> simplify(hypergeom([3/2,-n],[3],-x)):
T := (n,k) -> 4^(n-k)*coeff(h(n), x, n-k):
seq(print(seq(T(n,k), k=0..n)), n=0..9); # Peter Luschny, Feb 04 2015

Mathematica

T[n_, k_] := Binomial[n, k]*CatalanNumber[n-k+1]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 04 2015 *)

Formula

T(n,k) = binomial(n,k)*c(n-k+1), where c(m) = binomial(2m,m)/(m+1) is a Catalan number (A000108). Proof: There are c(n-k+1) binary trees with n-k edges. We can insert k vertical edges at the n-k+1 vertices (repetitions possible) in binomial(n-k+1+k-1,k) = binomial(n,k) ways.

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

Sum of terms in row n is A002212(n+1).

T(n,0) = A000108(n+1) (the Catalan numbers).

Sum_{k=0..n} k*T(n,k) = A026376(n) for n >= 1.

1/(1 - xy - 2x - x^2/(1 - xy - 2x - x^2/(1 - xy - 2x - x^2/(1 - xy - 2x - x^2/(1 - ... (continued fraction). - Paul Barry, Jan 28 2009

T(n,k) = 4^(n-k)*[x^(n-k)]hypergeom([3/2,-n],[3],-x). - Peter Luschny, Feb 04 2015

Extensions

Edited by N. J. A. Sloane at the suggestion of Andrew S. Plewe, Jun 13 2007

Edited and previous name moved to comments by Peter Luschny, Feb 03 2015