A126182 - OEIS

%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