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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A089732 Triangle read by rows: T(n,k) = number of peakless Motzkin paths of length n having k (1,1) steps (can be easily translated into RNA secondary structure terminology). Except for row 0, row n has ceil(n/2) entries. 4
1, 1, 1, 1, 1, 1, 3, 1, 6, 1, 1, 10, 6, 1, 15, 20, 1, 1, 21, 50, 10, 1, 28, 105, 50, 1, 1, 36, 196, 175, 15, 1, 45, 336, 490, 105, 1, 1, 55, 540, 1176, 490, 21, 1, 66, 825, 2520, 1764, 196, 1, 1, 78, 1210, 4950, 5292, 1176, 28, 1, 91, 1716, 9075, 13860, 5292, 336, 1, 1, 105 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,7

LINKS

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

A. Panayotopoulos and P. Vlamos, Cutting Degree of Meanders, Artificial Intelligence Applications and Innovations, IFIP Advances in Information and Communication Technology, Volume 382, 2012, pp 480-489; DOI 10.1007/978-3-642-33412-2_49. - From N. J. A. Sloane, Dec 29 2012

W. R. Schmitt and M. S. Waterman, Linear trees and RNA secondary structure, Discrete Appl. Math., 51, 317-323, 1994.

P. R. Stein and M. S. Waterman, On some new sequences generalizing the Catalan and Motzkin numbers, Discrete Math., 26 (1979), 261-272.

M. Vauchassade de Chaumont and G. Viennot, Polynomes orthogonaux at problemes d'enumeration en biologie moleculaire, Sem. Loth. Comb. B08l (1984) 79-86. [Formerly: Publ. I.R.M.A. Strasbourg, 1984, 229/S-08, p. 79-86.]

M. S. Waterman, Home Page (contains copies of his papers)

FORMULA

T(0, 0)=1; T(n, k)=binomial(n-k, k)*binomial(n-k, k+1)/(n-k) for 2k<=n-1. G.f.=g=(1-z+tz^2-sqrt(1-2z+z^2-2tz^2-2tz^3+t^2*z^4))/(2tz^2), solution of g=1+zg+tz^2*g(g-1). G.f.=1+r(tz, z), where r(t, z) is the Narayana function defined by r=z(1+r)(1+tr). Column g.f.'s are 1/(1-z) for column 0 and z^(k+1)*N_k(z)/(1-z)^(2k+1) for columns k=1, 2, ..., where N_k(z)=(1/k)sum(binomial(k, j)*binomial(k, j-1)*z^(j-1), j=1..k) are the Narayana polynomials.

G.f. g(z, t) = Sum_{n, k} T(n, k)z^n*t^k = 1/(1 - z + z^2*t(1-g(z, t))). - Michael Somos, Sep 08 2005

Given g.f. g(z, t) then G=z*g(z, t) series reversion in z is -G(-z, t). - Michael Somos, Sep 08 2005

Given g.f. g(z, t) then G=z*g(z, t) satisfies G = z + z*G/(1-t*z*G). - Michael Somos, Sep 08 2005

EXAMPLE

T(4,1)=3 because we have UHDH, HUHD and UHHD, where U=(1,1), D=(1,-1), H=(1,0).

1; 1; 1; 1,1; 1,3; 1,6,1; 1,10,6; 1,15,20,1; 1,21,50,10; 1,28,105,50,1;

Or as irregular table whose diagonals are rows of A001263:

[1] 1

[2] 1

[3] 1, 1

[4] 1, 3,

[5] 1, 6, 1

[6] 1, 10, 6

[7] 1, 15, 20, 1

[8] 1, 21, 50, 10

[9] 1, 28, 105, 50, 1  - Tom Copeland, May 14 2012

PROG

(PARI) {T(n, k)=local(A); if(n<1, k==0, n--; A=1+O(x); for(i=1, (n+1)\2, A = 1/(1/(1+x*x*y*A)-x)); polcoeff(polcoeff(A, n), k))} /* Michael Somos, Sep 08 2005 */

CROSSREFS

Row sums give A004148.

Sequence in context: A128489 A130541 A034839 * A158905 A098076 A171852

Adjacent sequences:  A089729 A089730 A089731 * A089733 A089734 A089735

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Jan 07 2004

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 22:41 EST 2018. Contains 299627 sequences. (Running on oeis4.)