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