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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A126182 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. 4
1, 2, 1, 4, 5, 1, 8, 18, 9, 1, 16, 56, 50, 14, 1, 32, 160, 220, 110, 20, 1, 64, 432, 840, 645, 210, 27, 1, 128, 1120, 2912, 3150, 1575, 364, 35, 1, 256, 2816, 9408, 13552, 9534, 3388, 588, 44, 1, 512, 6912, 28800, 53088, 49644, 24822, 6636, 900, 54, 1 (list; table; graph; refs; listen; history; text; internal format)
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

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

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

Cf. A001263, A007318, A002212, A001793, A006974, A026379.

Cf. A128718, A026378, A126216.

Sequence in context: A123876 A114164 A176667 * A154342 A143494 A124960

Adjacent sequences:  A126179 A126180 A126181 * A126183 A126184 A126185

KEYWORD

nonn,tabl,nice

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 20 07:42 EDT 2019. Contains 321345 sequences. (Running on oeis4.)