|
%I #37 Dec 13 2015 16:07:42
%S 1,2,1,4,5,1,8,18,9,1,16,56,50,14,1,32,160,220,110,20,1,64,432,840,
%T 645,210,27,1,128,1120,2912,3150,1575,364,35,1,256,2816,9408,13552,
%U 9534,3388,588,44,1,512,6912,28800,53088,49644,24822,6636,900,54,1
%N Let P be Pascal's triangle A007318 and let N be Narayana's triangle A001263, both regarded as lower triangular matrices. Sequence gives triangle obtained from P*N, read by rows.
%C 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.
%C 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).
%C 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).
%C A126216 = N * P. - _Gary W. Adamson_, Nov 30 2007
%H E. Deutsch, E. Munarini, S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.jspi.2010.01.015">Skew Dyck paths</a>, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.
%H M. Dziemianczuk, <a href="http://dx.doi.org/10.1016/j.disc.2014.07.024">Enumerations of plane trees with multiple edges and Raney lattice paths</a>, Discrete Mathematics 337 (2014): 9-24.
%H F. Harary and R. C. Read, <a href="http://dx.doi.org/10.1017/S0013091500009135">The enumeration of tree-like polyhexes</a>, Proc. Edinburgh Math. Soc. (2) 17 (1970), 1-13.
%F 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.
%F G.f. G=G(t,z) satisfies G = 1 + (t+2)*z*G + t*z^2*G^2.
%F E.g.f.: exp((t+2)*x)*BesselI_{1}(2*sqrt(t)*x)/(sqrt(t)*x). - _Peter Luschny_, Oct 29 2014
%F 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.
%e The triangle P begins
%e 1,
%e 1, 1
%e 1, 2, 1
%e 1, 3, 3, 1, ...
%e and T begins
%e 1,
%e 1, 1,
%e 1, 3, 1,
%e 1, 6, 6, 1,
%e 1, 10, 20, 10, 1, ...
%e The product P*T gives
%e 1,
%e 2, 1,
%e 4, 5, 1,
%e 8, 18, 9, 1,
%e 16, 56, 50, 14, 1, ...
%p 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
%t 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 *)
%t 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_ *)
%o (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
%Y Cf. A001263, A007318, A002212, A001793, A006974, A026379.
%Y Cf. A128718, A026378, A126216.
%K nonn,tabl,nice
%O 0,2
%A _Emeric Deutsch_, Dec 19 2006, Mar 30 2007
%E New definition in terms of P and N from _Philippe Deléham_, Jun 30 2007
%E Edited by _N. J. A. Sloane_, Jul 22 2007
|
