cp's OEIS Frontend

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.

%I A059231 #123 Aug 22 2025 04:26:13
%S A059231 1,1,5,29,185,1257,8925,65445,491825,3768209,29324405,231153133,
%T A059231 1841801065,14810069497,120029657805,979470140661,8040831465825,
%U A059231 66361595715105,550284185213925,4582462506008253,38306388126997785,321327658068506121,2703925940081270205
%N 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.
%C A059231 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
%C A059231 a(n) = A059450(n, n). - _Michael Somos_, Mar 06 2004
%C A059231 The Hankel transform of this sequence is 4^binomial(n+1,2). - _Philippe Deléham_, Oct 29 2007
%C A059231 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
%C A059231 Shifts left when INVERT transform applied four times. - _Benedict W. J. Irwin_, Feb 02 2016
%H A059231 Vincenzo Librandi, <a href="/A059231/b059231.txt">Table of n, a(n) for n = 0..1000</a>
%H A059231 Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Barry/barry91.html">On Integer-Sequence-Based Constructions of Generalized Pascal Triangles</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
%H A059231 Paul Barry and Aoife Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Barry2/barry126.html">A Note on Narayana Triangles and Related Polynomials, Riordan Arrays, and MIMO Capacity Calculations</a>, J. Int. Seq. 14 (2011), Article 11.3.8.
%H A059231 Paul Barry and Aoife Hennessy, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Barry2/barry190r.html">Generalized Narayana Polynomials, Riordan Arrays, and Lattice Paths</a>, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.8.
%H A059231 Zhi Chen and Hao Pan, <a href="https://arxiv.org/abs/1608.02448">Identities involving weighted Catalan, Schroder and Motzkin paths</a>, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=1, b=4.
%H A059231 Curtis Coker, <a href="http://dx.doi.org/10.1016/S0012-365X(03)00037-2">Enumerating a class of lattice paths</a>, Discrete Math., 271 (2003), 13-28 (the sequence d_n).
%H A059231 Curtis Coker, <a href="http://dx.doi.org/10.1016/j.disc.2003.12.008">A family of eigensequences</a>, Discrete Math. 282 (2004), 249-250.
%H A059231 Aoife Hennessy, <a href="http://repository.wit.ie/1693/1/AoifeThesis.pdf">A Study of Riordan Arrays with Applications to Continued Fractions, Orthogonal Polynomials and Lattice Paths</a>, Ph. D. Thesis, Waterford Institute of Technology, Oct. 2011.
%H A059231 Joseph P. S. Kung and Anna de Mier, <a href="http://dx.doi.org/10.1016/j.jcta.2012.08.010">Catalan lattice paths with rook, bishop and spider steps</a>, J. Comb. Theor., Series A (2013) Vol. 120, Issue 2, 379-389.
%H A059231 Gregory J. Morrow, <a href="https://doi.org/10.1016/j.spa.2014.12.005">Laws relating runs and steps in gambler’s ruin</a>, Stochastic Proc. Appl. (2024) Vol. 125, Issue 5, 2010-2025.
%H A059231 Gregory Morrow, <a href="https://faculty.uccs.edu/gmorrow/wp-content/uploads/sites/19/2024/08/Prob_Distrns__Int_Seqs_related_to_Rook_Paths_Aug_9_2024.pdf">Some probability distributions and integer sequences related to rook paths</a>, Univ. Colorado Springs (2024). See pp. 1, 4, 15, 22. <a href="https://doi.org/10.54550/ECA2025V5S2R12">DOI</a>
%H A059231 Michael Z. Spivey and Laura L. Steil, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Spivey/spivey7.html">The k-Binomial Transforms and the Hankel Transform</a>, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.
%H A059231 Paveł Szabłowski, <a href="https://cdm.ucalgary.ca/article/view/76214">Beta distributions whose moment sequences are related to integer sequences listed in the OEIS</a>, Contrib. Disc. Math. (2024) Vol. 19, No. 4, 85-109. See p. 98.
%H A059231 Wen-jin Woan, <a href="https://zbmath.org/?q=an:01735667">Diagonal lattice paths</a>, Congr. Numer. 151 (2001) 173-178.
%F A059231 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
%F A059231 a(n) = 3^n/2*LegendreP(n, -1, 5/3). - _Vladeta Jovovic_, Sep 17 2003
%F A059231 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
%F A059231 a(n) = Sum_{k=0..n} A088617(n, k)*4^k*(-3)^(n-k). - _Philippe Deléham_, Jan 21 2004
%F A059231 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
%F A059231 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
%F A059231 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
%F A059231 a(n) = upper left term in M^n, M = the production matrix:
%F A059231   1, 1
%F A059231   4, 4, 4
%F A059231   1, 1, 1, 1
%F A059231   4, 4, 4, 4, 4
%F A059231   1, 1, 1, 1, 1, 1
%F A059231   ... - _Gary W. Adamson_, Jul 08 2011
%F A059231 a(n) is the sum of top row terms of Q^(n-1), where Q = the following infinite square production matrix:
%F A059231   1, 4, 0, 0, 0, ...
%F A059231   1, 1, 4, 0, 0, ...
%F A059231   1, 1, 1, 4, 0, ...
%F A059231   1, 1, 1, 1, 4, ...
%F A059231   ... - _Gary W. Adamson_, Aug 23 2011
%F A059231 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
%F A059231 a(n) ~ sqrt(2)*3^(2*n+1)/(8*sqrt(Pi)*n^(3/2)). - _Vaclav Kotesovec_, Oct 11 2012
%F A059231 a(n) = A127846(n) for n>0. - _Philippe Deléham_, Apr 03 2013
%F A059231 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
%F A059231 G.f.: 1/(1 - x/(1 - 4*x/(1 - x/(1 - 4*x/(1 - x/(1 - ...)))))), a continued fraction. - _Ilya Gutkovskiy_, Aug 10 2017
%e A059231 a(3) = 29 since the top row of Q^2 = (5, 8, 16, 0, 0, 0, ...), and 5 + 8 + 16 = 29.
%p A059231 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:
%p A059231 A059231_list := proc(n) local j, a, w; a := array(0..n); a[0] := 1;
%p A059231 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;
%p A059231 convert(a, list) end: A059231_list(20); # _Peter Luschny_, May 19 2011
%t A059231 Join[{1},Table[-I 3^n/2LegendreP[n,-1,5/3],{n,40}]] (* _Harvey P. Dale_, Jun 09 2011 *)
%t A059231 Table[Hypergeometric2F1[-n, 1 - n, 2, 4], {n, 0, 22}] (* _Arkadiusz Wesolowski_, Aug 13 2012 *)
%o A059231 (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 */
%o A059231 (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 */
%o A059231 (Sage) # Algorithm of L. Seidel (1877)
%o A059231 def A059231_list(n) :
%o A059231     D = [0]*(n+2); D[1] = 1
%o A059231     R = []; b = False; h = 1
%o A059231     for i in range(2*n) :
%o A059231         if b :
%o A059231             for k in range(1, h, 1) : D[k] += 2*D[k+1]
%o A059231         else :
%o A059231             for k in range(h, 0, -1) : D[k] += 2*D[k-1]
%o A059231             h += 1
%o A059231         b = not b
%o A059231         if b : R.append(D[1])
%o A059231     return R
%o A059231 A059231_list(23)  # _Peter Luschny_, Oct 19 2012
%Y A059231 Cf. A000108, A001003, A007564, A127846.
%Y A059231 Row sums of A086873.
%Y A059231 Column k=2 of A227578. - _Alois P. Heinz_, Jul 17 2013
%K A059231 nonn,easy,changed
%O A059231 0,3
%A A059231 _Wenjin Woan_, Jan 20 2001