The OEIS is supported by the many generous donors to the OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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. 25
 1, 1, 5, 29, 185, 1257, 8925, 65445, 491825, 3768209, 29324405, 231153133, 1841801065, 14810069497, 120029657805, 979470140661, 8040831465825, 66361595715105, 550284185213925, 4582462506008253, 38306388126997785, 321327658068506121, 2703925940081270205 (list; graph; refs; listen; history; text; internal format)
 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. P. Barry, A. Hennessy, A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations , J. Int. Seq. 14 (2011) # 11.3.8 Paul Barry and Aoife Hennessy, Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths, Journal of Integer Sequences, Vol. 15, 2012, #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 := 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 = *(n+2); D = 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)     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

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

Last modified July 6 11:27 EDT 2022. Contains 355110 sequences. (Running on oeis4.)