|
%I #35 Jul 21 2019 15:35:07
%S 1,2,1,5,4,1,14,15,6,1,42,56,30,8,1,132,210,140,50,10,1,429,792,630,
%T 280,75,12,1,1430,3003,2772,1470,490,105,14,1,4862,11440,12012,7392,
%U 2940,784,140,16,1,16796,43758,51480,36036,16632,5292,1176,180,18,1,58786
%N Triangle read by rows, T(n,k) = C(n,k)*Catalan(n-k+1), n >= 0, 0 <= k <= n.
%C 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).
%C 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.
%C 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).
%H F. Harary and R. C. Read, <a href="http://dx.doi.org/10.1017/S0013091500009135">The enumeration of tree-like polyhexes</a>, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
%F 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.
%F G.f.: G = G(t,z) satisfies G = 1 + (2+t)*z*G + z^2*G^2.
%F Sum of terms in row n is A002212(n+1).
%F T(n,0) = A000108(n+1) (the Catalan numbers).
%F Sum_{k=0..n} k*T(n,k) = A026376(n) for n >= 1.
%F 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
%F T(n,k) = 4^(n-k)*[x^(n-k)]hypergeom([3/2,-n],[3],-x). - _Peter Luschny_, Feb 04 2015
%e Triangle starts:
%e 1;
%e 2, 1;
%e 5, 4, 1;
%e 14, 15, 6, 1;
%e 42, 56, 30, 8, 1;
%p 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
%p # Second implementation:
%p h := n -> simplify(hypergeom([3/2,-n],[3],-x)):
%p T := (n,k) -> 4^(n-k)*coeff(h(n), x, n-k):
%p seq(print(seq(T(n,k), k=0..n)), n=0..9); # _Peter Luschny_, Feb 04 2015
%t 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 *)
%Y Mirror image of A108198.
%Y Cf. A002212, A000108, A026376.
%K nonn,tabl
%O 0,2
%A _Emeric Deutsch_, Dec 19 2006, Mar 30 2007
%E Edited by _N. J. A. Sloane_ at the suggestion of _Andrew S. Plewe_, Jun 13 2007
%E Edited and previous name moved to comments by _Peter Luschny_, Feb 03 2015
|
