

A126181


Triangle read by rows, T(n,k) = C(n,k)*Catalan(nk+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 treelike polyhexes; see the HararyRead 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 <= n1). A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the xaxis, 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

Table of n, a(n) for n=0..55.
F. Harary and R. C. Read, The enumeration of treelike polyhexes, Proc. Edinburgh Math. Soc. (2) 17 (1970), 113.


FORMULA

T(n,k) = binomial(n,k)*c(nk+1), where c(m) = binomial(2m,m)/(m+1) is a Catalan number (A000108). Proof: There are c(nk+1) binary trees with nk edges. We can insert k vertical edges at the nk+1 vertices (repetitions possible) in binom(nk+1+k1,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^(nk)*[x^(nk)]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(nk+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^(nk)*coeff(h(n), x, nk):
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[nk+1]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* JeanFranç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 Plewe, Jun 13 2007
Edited and previous name moved to comments by Peter Luschny, Feb 03 2015


STATUS

approved



