OFFSET
0,2
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).
LINKS
F. Harary and R. C. Read, The enumeration of tree-like polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
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
EXAMPLE
Triangle starts:
1;
2, 1;
5, 4, 1;
14, 15, 6, 1;
42, 56, 30, 8, 1;
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 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Dec 19 2006, Mar 30 2007
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
STATUS
approved