A059231 Number of different lattice paths running from (0,0) to (n,0) using steps from S = {(k,k) or (k,-k): k positive integer} that never go below the x-axis.

1, 1, 5, 29, 185, 1257, 8925, 65445, 491825, 3768209, 29324405, 231153133, 1841801065, 14810069497, 120029657805, 979470140661, 8040831465825, 66361595715105, 550284185213925, 4582462506008253, 38306388126997785, 321327658068506121, 2703925940081270205

Offset

0,3

Comments

If y = x*A(x) then 4*y^2 - (1 + 3*x)*y + x = 0 and x = y*(1 - 4*y) / (1 - 3*y). - Michael Somos, Sep 28 2003

a(n) = A059450(n, n). - Michael Somos, Mar 06 2004

The Hankel transform of this sequence is 4^binomial(n+1,2). - Philippe Deléham, Oct 29 2007

a(n) is the number of Schroder paths of semilength n in which there are no (2,0)-steps at level 0 and at a higher level they come in 3 colors. Example: a(2)=5 because we have UDUD, UUDD, UBD, UGD, and URD, where U=(1,1), D=(1,-1), while B, G, and R are, respectively, blue, green, and red (2,0)-steps. - Emeric Deutsch, May 02 2011

Shifts left when INVERT transform applied four times. - Benedict W. J. Irwin, Feb 02 2016

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.

Paul Barry and Aoife Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations, J. Int. Seq. 14 (2011), Article 11.3.8.

Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.8.

Z. Chen, H. Pan, Identities involving weighted Catalan-Schroder and Motzkin Paths, arXiv:1608.02448 [math.CO], (2016), eq. (1.13), a=1, b=4.

C. Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28 (the sequence d_n).

C. Coker, A family of eigensequences, Discrete Math. 282 (2004), 249-250.

Aoife Hennessy, A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.

J. P. S. Kung and A. de Mier, Catalan lattice paths with rook, bishop and spider steps, Journal of Combinatorial Theory, Series A 120 (2013) 379-389.

G. L. Morrow, Laws relating runs and steps in gambler's ruin, Stochastic Processes and their Applications, 125 (2015) 2010-2025.

Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.

W.-j. Woan, Diagonal lattice paths, Congr. Numer. 151 (2001) 173-178

Formula

a(n) = Sum_{k=0..n} 4^k*N(n, k) where N(n, k) = (1/n)*binomial(n, k)*binomial(n, k+1) are the Narayana numbers (A001263). - Benoit Cloitre, May 10 2003

a(n) = 3^n/2*LegendreP(n, -1, 5/3). - Vladeta Jovovic, Sep 17 2003

G.f.: (1 + 3*x - sqrt(1 - 10*x + 9*x^2)) / (8*x) = 2 / (1 + 3*x + sqrt(1 - 10*x + 9*x^2)). - Michael Somos, Sep 28 2003

a(n) = Sum_{k=0..n} A088617(n, k)*4^k*(-3)^(n-k). - Philippe Deléham, Jan 21 2004

With offset 1: a(1)=1, a(n) = -3*a(n-1) + 4*Sum_{i=1..n-1} a(i)*a(n-i). - Benoit Cloitre, Mar 16 2004

D-finite with recurrence a(n) = (5(2n-1)a(n-1) - 9(n-2)a(n-2))/(n+1) for n>=2; a(0)=a(1)=1. - Emeric Deutsch, Mar 20 2004

Moment representation: a(n)=(1/(8*Pi))*Int(x^n*sqrt(-x^2+10x-9)/x,x,1,9)+(3/4)*0^n. - Paul Barry, Sep 30 2009

a(n) = upper left term in M^n, M = the production matrix:

1, 1

4, 4, 4

1, 1, 1, 1

4, 4, 4, 4, 4

1, 1, 1, 1, 1, 1

... - Gary W. Adamson, Jul 08 2011

a(n) is the sum of top row terms of Q^(n-1), where Q = the following infinite square production matrix:

1, 4, 0, 0, 0, ...

1, 1, 4, 0, 0, ...

1, 1, 1, 4, 0, ...

1, 1, 1, 1, 4, ...

... - Gary W. Adamson, Aug 23 2011

G.f.: (1+3*x-sqrt(9*x^2-10*x+1))/(8*x)=(1+3*x -G(0))/(4*x) ; G(k)= 1+x*3-x*4/G(k+1); (continued fraction, 1-step ). - Sergei N. Gladkovskii, Jan 05 2012

a(n) ~ sqrt(2)*3^(2*n+1)/(8*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Oct 11 2012

a(n) = A127846(n) for n>0. - Philippe Deléham, Apr 03 2013

0 = a(n)*(+81*a(n+1) - 225*a(n+2) + 36*a(n+3)) + a(n+1)*(+45*a(n+1) + 82*a(n+2) - 25*a(n+3)) + a(n+2)*(+5*a(n+2) + a(n+3)) for all n>=0. - Michael Somos, Aug 25 2014

G.f.: 1/(1 - x/(1 - 4*x/(1 - x/(1 - 4*x/(1 - x/(1 - ...)))))), a continued fraction. - Ilya Gutkovskiy, Aug 10 2017

Example

a(3) = 29 since the top row of Q^2 = (5, 8, 16, 0, 0, 0, ...), and 5 + 8 + 16 = 29.

Maple

gf := (1+3*x-sqrt(9*x^2-10*x+1))/(8*x): s := series(gf, x, 100): for i from 0 to 50 do printf(`%d, `, coeff(s, x, i)) od:
A059231_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
for w from 1 to n do a[w] := a[w-1]+4*add(a[j]*a[w-j-1], j=1..w-1) od;
convert(a, list) end: A059231_list(20); # Peter Luschny, May 19 2011

Mathematica

Join[{1}, Table[-I 3^n/2LegendreP[n, -1, 5/3], {n, 40}]] (* Harvey P. Dale, Jun 09 2011 *)
Table[Hypergeometric2F1[-n, 1 - n, 2, 4], {n, 0, 22}] (* Arkadiusz Wesolowski, Aug 13 2012 *)

Prog

(PARI) {a(n) = if( n<0, 0, polcoeff( (1 + 3*x - sqrt(1 - 10*x + 9*x^2 + x^2 * O(x^n))) / (8*x), n))}; /* Michael Somos, Sep 28 2003 */
(PARI) {a(n) = if( n<0, 0, n++; polcoeff( serreverse( x * (1 - 4*x) / (1 - 3*x) + x * O(x^n)), n))}; /* Michael Somos, Sep 28 2003 */
(Sage) # Algorithm of L. Seidel (1877)
def A059231_list(n) :
    D = [0]*(n+2); D[1] = 1
    R = []; b = False; h = 1
    for i in range(2*n) :
        if b :
            for k in range(1, h, 1) : D[k] += 2*D[k+1]
        else :
            for k in range(h, 0, -1) : D[k] += 2*D[k-1]
            h += 1
        b = not b
        if b : R.append(D[1])
    return R
A059231_list(23)  # Peter Luschny, Oct 19 2012

Crossrefs

Cf. A000108, A001003, A007564, A127846.

Row sums of A086873.

Column k=2 of A227578. - Alois P. Heinz, Jul 17 2013

Sequence in context: A175891 A081336 A127846 * A137573 A234317 A346845

Adjacent sequences: A059228 A059229 A059230 * A059232 A059233 A059234

Keyword

nonn,easy

Author

Wenjin Woan, Jan 20 2001

Status

approved