login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=0..55.

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 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.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 23 21:23 EST 2018. Contains 299588 sequences. (Running on oeis4.)