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.
Zhi Chen and Hao Pan, Identities involving weighted Catalan, Schroder and Motzkin paths, arXiv:1608.02448 [math.CO], 2016. See eq. (1.13), a=1, b=4.
Curtis Coker, Enumerating a class of lattice paths, Discrete Math., 271 (2003), 13-28 (the sequence d_n).
Curtis 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.
Joseph P. S. Kung and Anna de Mier, Catalan lattice paths with rook, bishop and spider steps, J. Comb. Theor., Series A (2013) Vol. 120, Issue 2, 379-389.
Gregory J. Morrow, Laws relating runs and steps in gambler’s ruin, Stochastic Proc. Appl. (2024) Vol. 125, Issue 5, 2010-2025.
Greg Morrow, Some probability distributions and integer sequences related to rook paths, Univ. Colorado Springs (2024). See pp. 1, 4, 15, 22.
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, J. Integ. Seqs. Vol. 9 (2006), #06.1.1.
Wen-jin 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
KEYWORD
nonn,easy
AUTHOR
Wenjin Woan, Jan 20 2001
STATUS
approved