OFFSET
0,2
COMMENTS
Also T(n,k) is number of hex trees with n edges and k left 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 reference). Accordingly, one can have left, vertical, or right edges.
Also (with a different offset) T(n,k) is the number of skew Dyck paths of semilength n and having k peaks (1<=k<=n). 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 the path is defined to be the number of its steps. E.g., T(3,2)=5 because we have (UD)U(UD)D, (UD)U(UD)L, U(UD)D(UD), U(UD)(UD)D and U(UD)(UD)L (the peaks are shown between parentheses).
Sum of terms in row n = A002212(n+1). T(n,1) = A001793(n); T(n,2) = A006974(n-2); Sum_{k=0..n}kT(n,k) = A026379(n+1).
A126216 = N * P. - Gary W. Adamson, Nov 30 2007
LINKS
E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
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) = (1/(n+1))*binomial(n+1,k)*Sum_{j=n-2k..n-k}2^j*binomial(k,n-k-j)*binomial(n+1-k,j) if 0 < k <= n; T(n,0) = 2^n.
G.f. G=G(t,z) satisfies G = 1 + (t+2)*z*G + t*z^2*G^2.
E.g.f.: exp((t+2)*x)*BesselI_{1}(2*sqrt(t)*x)/(sqrt(t)*x). - Peter Luschny, Oct 29 2014
G.f.: N(x/(1-x),y)-1)/x, where N(x,y) is the g.f. of Narayana's triangle A001263. - Vladimir Kruchinin, Apr 06 2015.
EXAMPLE
The triangle P begins
1,
1, 1
1, 2, 1
1, 3, 3, 1, ...
and T begins
1,
1, 1,
1, 3, 1,
1, 6, 6, 1,
1, 10, 20, 10, 1, ...
The product P*T gives
1,
2, 1,
4, 5, 1,
8, 18, 9, 1,
16, 56, 50, 14, 1, ...
MAPLE
T:=proc(n, k) if k=0 then 2^n elif k<=n then binomial(n+1, k)*sum(binomial(k, n-k-j)*binomial(n+1-k, j)*2^j, j=n-2*k..n-k)/(n+1) else 0 fi end: for n from 0 to 10 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form
MATHEMATICA
t[n_, 0] := 2^n; t[n_, k_] := Binomial[n+1, k]*Sum[Binomial[k, n-k-j]*Binomial[n+1-k, j]*2^j, {j, n-2*k, n-k}]/(n+1); Table[t[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jun 12 2013 *)
nmax = 10; n[x_, y_] := (1-x*(1+y) - Sqrt[(1-x*(1+y))^2 - 4*y*x^2])/(2*x); s = Series[(n[x/(1-x), y]-1)/x, {x, 0, nmax+1}, {y, 0, nmax+1}]; t[n_, k_] := SeriesCoefficient[s, {x, 0, n}, {y, 0, k}]; Table[t[n, k], {n, 0, nmax}, {k, 1, n+1}] // Flatten (* Jean-François Alcover, Apr 16 2015, after Vladimir Kruchinin *)
PROG
(PARI) tabl(nn) = {mP = matrix(nn, nn, n, k, binomial(n-1, k-1)); mN = matrix(nn, nn, n, k, binomial(n-1, k-1) * binomial(n, k-1) / k); mprod = mP*mN; for (n=1, nn, for (k=1, n, print1(mprod[n, k], ", "); ); print(); ); } \\ Michel Marcus, Apr 16 2015
CROSSREFS
KEYWORD
AUTHOR
Emeric Deutsch, Dec 19 2006, Mar 30 2007
EXTENSIONS
New definition in terms of P and N from Philippe Deléham, Jun 30 2007
Edited by N. J. A. Sloane, Jul 22 2007
STATUS
approved