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

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A091965 Triangle read by rows: T(n,k)=number of lattice paths from (0,0) to (n,k) that do not go below the line y=0 and consist of steps U=(1,1), D=(1,-1) and three types of steps H=(1,0) (left factors of 3-Motzkin steps). 33
1, 3, 1, 10, 6, 1, 36, 29, 9, 1, 137, 132, 57, 12, 1, 543, 590, 315, 94, 15, 1, 2219, 2628, 1629, 612, 140, 18, 1, 9285, 11732, 8127, 3605, 1050, 195, 21, 1, 39587, 52608, 39718, 19992, 6950, 1656, 259, 24, 1, 171369, 237129, 191754, 106644, 42498, 12177, 2457 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

T(n,0)=A002212(n+1), T(n,1)=A045445(n+1), Row sums give A026378.

The inverse is A207815. - Gary W. Adamson, Dec 17 2006 (corrected by Philippe Deléham, Feb 22 2012)

Reversal of A084536 . - Philippe Deléham, Mar 23 2007

Triangle T(n,k), 0<=k<=n, read by rows given by : T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0)=3*T(n-1,0)+T(n-1,1), T(n,k)=T(n-1,k-1)+3*T(n-1,k)+T(n-1,k+1) for k>=1 . - Philippe Deléham, Mar 27 2007

This triangle belongs to the family of triangles defined by: T(0,0)=1, T(n,k)=0 if k<0 or if k>n, T(n,0)=x*T(n-1,0)+T(n-1,1), T(n,k)=T(n-1,k-1)+y*T(n-1,k)+T(n-1,k+1) for k>=1 . Other triangles arise by choosing different values for (x,y): (0,0) -> A053121; (0,1) -> A089942; (0,2) -> A126093; (0,3) -> A126970; (1,0)-> A061554; (1,1) -> A064189; (1,2) -> A039599; (1,3) -> A110877; ((1,4) -> A124576; (2,0) -> A126075; (2,1) -> A038622; (2,2) -> A039598; (2,3) -> A124733; (2,4) -> A124575; (3,0) -> A126953; (3,1) -> A126954; (3,2) -> A111418; (3,3) -> A091965; (3,4) -> A124574; (4,3) -> A126791; (4,4) -> A052179; (4,5) -> A126331; (5,5) -> A125906 . - Philippe Deléham, Sep 25 2007

5^n = (n-th row terms) dot (first n+1 terms in (1,2,3,...)). Example for row 4: 5^4 = 625 = (137, 132, 57, 12, 1) dot (1, 2, 3, 4, 5) = (137 + 264 + 171 + 48 + 5) = 625. - Gary W. Adamson, Jun 15 2011

Riordan array ((1-3*x-sqrt(1-6*x+5*x^2))/(2*x^2), (1-3*x-sqrt(1-6*x+5*x^2))/(2*x)). - Philippe Deléham, Feb 19 2012

REFERENCES

A. Nkwanta, Lattice paths and RNA secondary structures, DIMACS Series in Discrete Math. and Theoretical Computer Science, 34, 1997, 137-147.

LINKS

Vincenzo Librandi, Rows n = 0..100, flattened

FORMULA

G.f.: G=2/(1-3*z-2*t*z+sqrt(1-6*z+5*z^2)). Alternatively, G=M/(1-t*z*M), where M=1+3*z*M+z^2*M^2.

Sum_{k, k>=0} T(m, k)*T(n, k) = T(m+n, 0) = A002212(m+n+1) . - Philippe Deléham, Sep 14 2005

The triangle may also be generated from M^n * [1,0,0,0...], where M = an infinite tridiagonal matrix with 1's in the super and subdiagonals and [3,3,3...] in the main diagonal. - Gary W. Adamson, Dec 17 2006

Sum_{k, 0<=k<=n}T(n,k)*(k+1)=5^n . - Philippe Deléham, Mar 27 2007

Sum_{k, 0<=k<=n}T(n,k)*x^k = A117641(n), A033321(n), A007317(n), A002212(n+1), A026378(n+1) for x = -3, -2, -1, 0, 1 respectively. [From Philippe Deléham, Nov 28 2009]

T(n,k) = (k+1)*sum(m=k..n, (binomial(2*(m+1),m-k)*binomial(n,m))/(m+1)). [From Vladimir Kruchinin, Oct 08 2011]

EXAMPLE

Triangle begins:

[1],

[3, 1],

[10, 6, 1],

[36, 29, 9, 1],

[137, 132, 57, 12, 1],

[543, 590, 315, 94, 15, 1],

[2219, 2628, 1629, 612, 140, 18, 1]

T(3,1)=29 because we have UDU, UUD, 9 HHU paths, 9 HUH paths and 9 UHH paths.

Production matrix begins

3, 1

1, 3, 1

0, 1, 3, 1

0, 0, 1, 3, 1

0, 0, 0, 1, 3, 1

0, 0, 0, 0, 1, 3, 1

0, 0, 0, 0, 0, 1, 3, 1

0, 0, 0, 0, 0, 0, 1, 3, 1

0, 0, 0, 0, 0, 0, 0, 1, 3, 1

0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 1

- From Philippe Deléham, Nov 07 2011

MATHEMATICA

nmax = 9; t[n_, k_] := ((k+1)*n!*Hypergeometric2F1[k+3/2, k-n, 2k+3, -4]) / ((k+1)!*(n-k)!); Flatten[ Table[ t[n, k], {n, 0, nmax}, {k, 0, n}]] (* Jean-François Alcover, Nov 14 2011, after Vladimir Kruchinin *)

PROG

(Maxima)

T(n, k):=(k+1)*sum((binomial(2*(m+1), m-k)*binomial(n, m))/(m+1), m, k, n); [From Vladimir Kruchinin, Oct 08 2011]

(Sage)

@CachedFunction

def A091965(n, k):

    if n==0 and k==0: return 1

    if k<0 or k>n: return 0

    if k==0: return 3*A091965(n-1, 0)+A091965(n-1, 1)

    return A091965(n-1, k-1)+3*A091965(n-1, k)+A091965(n-1, k+1)

for n in (0..7):

    [A091965(n, k) for k in (0..n)] # Peter Luschny, Nov 05 2012

CROSSREFS

Cf. A002212, A045445, A026378.

Cf. A123965.

Sequence in context: A134283 A035324 A171814 * A171568 A107056 A116384

Adjacent sequences:  A091962 A091963 A091964 * A091966 A091967 A091968

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Mar 13 2004

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified November 1 01:27 EDT 2014. Contains 248882 sequences.