This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A126181 Triangle read by rows, T(n,k) = C(n,k)*Catalan(n-k+1), n >= 0, 0 <= k <= n. 1
 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 (list; table; graph; refs; listen; history; text; internal format)
 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 binom(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 Mirror image of A108198. Cf. A002212, A000108, A026376. Sequence in context: A039598 A128738 A193673 * A154930 A104259 A137650 Adjacent sequences:  A126178 A126179 A126180 * A126182 A126183 A126184 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 23 01:24 EDT 2018. Contains 316518 sequences. (Running on oeis4.)