|
| |
|
|
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
|
|
|
|
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 binomial(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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Edited and previous name moved to comments by Peter Luschny, Feb 03 2015
|
|
|
STATUS
|
approved
|
| |
|
|
