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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A110470 Triangle, read by rows, where the g.f. of diagonal n, D_n(x) and the g.f. of row n-1, R_{n-1}(x), are related by: D_n(x) = R_{n-1}(x) / (1-x)^(n+1) for n>0 and the g.f. of the main diagonal is D_0(x) = 1/(1-x). 0
1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 6, 9, 4, 1, 1, 9, 19, 16, 5, 1, 1, 12, 38, 44, 25, 6, 1, 1, 16, 66, 111, 85, 36, 7, 1, 1, 20, 110, 240, 260, 146, 49, 8, 1, 1, 25, 170, 485, 676, 526, 231, 64, 9, 1, 1, 30, 255, 900, 1615, 1602, 959, 344, 81, 10, 1, 1, 36, 365, 1590, 3515, 4432 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Row sums form the Motzkin numbers (A001263).

With offset n>=1 and k>=0, T(n,k) is the number of Motzkin n-paths (A001006) with k weak valleys. A weak valley in a Motzkin path is an interior vertex whose following step has nonnegative slope and whose preceding step has nonpositive slope. For example, T(4,1)=4 counts F.UFD, UD.UD, UFD.F, UF.FD (U=upstep, D=downstep, F=flatstep, dots indicate weak valleys). - David Callan, Jun 07 2006

LINKS

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

L. Ferrari, E. Munarini, Enumeration of Edges in Some Lattices of Paths, J. Int. Seq. 17 (2014) #14.1.5

FORMULA

T(n, k) = Sum_{j=0..n-k-1} C(n-j, k-j)*T(n-k-1, j).

G.f. of column k>0: [Sum_{j=0..k-1} A001263(k-1, j)*x^(2*j)] / [(1-x)^(2*n+1)*(1+x)^n].

EXAMPLE

T(6,3) = T(3,0)*C(7,3) + T(3,1)*C(6,2) + T(3,2)*C(5,1) + T(3,3)*C(4,0)

= 1*35 + 4*15 + 3*5 + 1*1 = 111.

Triangle begins:

1;

1, 1;

1, 2, 1;

1, 4, 3, 1;

1, 6, 9, 4, 1;

1, 9, 19, 16, 5, 1;

1, 12, 38, 44, 25, 6, 1;

1, 16, 66, 111, 85, 36, 7, 1;

1, 20, 110, 240, 260, 146, 49, 8, 1;

1, 25, 170, 485, 676, 526, 231, 64, 9, 1; ...

Row sums form the Motzkin numbers:

{1,2,4,9,21,51,127,323,835,2188,...}.

G.f. of columns are:

column 1: 1/((1-x)^3*(1+x)^1);

column 2: (1 + x^2)/((1-x)^5*(1+x)^2);

column 3: (1 + 3*x^2 + x^4)/((1-x)^7*(1+x)^3);

column 4: (1 + 6*x^2 + 6*x^4 + x^6)/((1-x)^9*(1+x)^4);

column 5: (1 + 10*x^2 + 20*x^4 + 10*x^6 + x^8)/((1-x)^11*(1+x)^5); ...

where the coefficients in the above numerator polynomials form the Narayana triangle A001263:

1;

1, 1;

1, 3, 1;

1, 6, 6, 1;

1, 10, 20, 10, 1; ...

PROG

(PARI) T(n, k)=if(n<k || k<0, 0, if(k==0 || k==n, 1, sum(j=0, n-k-1, T(n-k-1, j)*binomial(n-j, k-j)); ))

(PARI) T(n, k)=local(X=x+x*O(x^n)); if(n<k || k<0, 0, if(k==0 || k==n, 1, polcoeff(x^k*sum(j=0, k-1, binomial(k-1, j)*binomial(k, j)/(j+1)*x^(2*j)) /((1-X)^(k+1)*(1-X^2)^k), n); ))

CROSSREFS

Cf. A001006 (Motzkin), A001263 (Narayana triangle).

Sequence in context: A177976 A034781 A058717 * A055080 A034367 A034371

Adjacent sequences:  A110467 A110468 A110469 * A110471 A110472 A110473

KEYWORD

nonn,tabl

AUTHOR

Paul D. Hanna, Jul 24 2005

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 January 20 12:32 EST 2019. Contains 319330 sequences. (Running on oeis4.)