This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A052709 Expansion of (1-sqrt(1-4x-4x^2))/(2(1+x)). 23
 0, 1, 1, 3, 9, 31, 113, 431, 1697, 6847, 28161, 117631, 497665, 2128127, 9183489, 39940863, 174897665, 770452479, 3411959809, 15181264895, 67833868289, 304256253951, 1369404661761, 6182858317823, 27995941060609 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS A simple context-free grammar. Number of lattice paths from (0,0) to (2n-2,0) that stay (weakly) in the first quadrant and such that each step is either U=(1,1),D=(1,-1), or L=(3,1). Equivalently, underdiagonal lattice paths from (0,0) to (n-1,n-1) and such that each step is either (1,0),(0,1), or (2,1). E.g. a(4)=9 because in addition to the five Dyck paths from (0,0) to (6,0) [UDUDUD, UDUUDD, UUDDUD, UUDUDD, UUUDDD] we have LDUD, LUDD, ULDD and UDLD. - Emeric Deutsch, Dec 21 2003 Hankel transform of a(n+1) is A006125(n+1). - Paul Barry, Apr 01 2007 Also, a(n+1) is the number of walks from (0,0) to (n,0) using steps (1,1), (1,-1) and (0,-1). See the U(n,k) array in A071943, where A052709(n+1) = U(n,0). - N. J. A. Sloane, Mar 29 2013 Diagonal sums of triangle in A085880. - Philippe Deléham, Nov 15 2013 LINKS N. J. A. Sloane, Table of n, a(n) for n = 0..499 Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, Matteo Silimbani, Ascending runs in permutations and valued Dyck paths, Ars Mathematica Contemporanea (2019) Vol. 16, No. 2, 445-463. Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385. Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018. Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara, Michael D. Weiner, Enumeration of colored Dyck paths via partial Bell polynomials, arXiv:1602.03550 [math.CO], 2016. Xiang-Ke Chang, X.-B. Hu, H. Lei, Y.-N. Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8. Brian Drake, Limits of areas under lattice paths, Discrete Math. 309 (2009), no. 12, 3936-3953. M. Dziemianczuk, On Directed Lattice Paths With Additional Vertical Steps, arXiv preprint arXiv:1410.5747 [math.CO], 2014. James East, Nicholas Ham, Lattice paths and submonoids of Z^2, arXiv:1811.05735 [math.CO], 2018. L. Ferrari, E. Pergola, R. Pinzani and S. Rinaldi, Jumping succession rules and their generating functions, Discrete Math., 271 (2003), 29-50. Nancy S. S. Gu, Nelson Y. Li, and Toufik Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221. INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 664 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. - N. J. A. Sloane, Dec 27 2012 D. Merlini, D. G. Rogers, R. Sprugnoli and M. C. Verri, On some alternative characterizations of Riordan arrays, Canad. J. Math., 49 (1997), 301-320. FORMULA a(n) = sum((2*n-2-2*k)!/k!/(n-k)!/(n-1-2*k)!, k=0..floor((n-1)/2)). - Emeric Deutsch, Nov 14 2001 n*a(n) = (3*n-6)*a(n-1)+(8*n-18)*a(n-2)+(4*n-12)*a(n-3), n>2. a(1)=a(2)=1. a(n) = b(1)*a(n-1)+b(2)*a(n-2)+...+b(n-1)*a(1) for n>1 where b(n)=A025227(n). G.f.: A(x) = x/(1-(1+x)*A(x)). [Paul D. Hanna, Aug 16 2002] G.f.: A(x) = x/(1-z/(1-z/(1-z/(...)))) where z=x+x^2 (continued fraction). [Paul D. Hanna, Aug 16 2002; revised by Joerg Arndt, Mar 18 2011]. a(n+1) = sum{k=0..n, C(k)*C(k, n-k)} - Paul Barry, Feb 22 2005 G.f. is x*c(x*(1+x)) where c(x) is the g.f. of A000108. Row sums of A117434. - Paul Barry, Mar 14 2006 a(n+1) = (1/(2*Pi))*int(x^n*(4+4x-x^2)/(2(1+x)),x,2-2*sqrt(2),2+2*sqrt(2)); - Paul Barry, Apr 01 2007 a(n), n>0 = upper left term in M^(n-1), where M = an infinite square production matrix as follows: 1, 1, 0, 0, 0, 0,... 2, 1, 1, 0, 0, 0,... 2, 2, 1, 1, 0, 0,... 2, 2, 2, 1, 1, 0,... 2, 2, 2, 2, 1, 1,... ... - Gary W. Adamson, Jul 22 2011 G.f.: x*Q(0), where Q(k)= 1 + (4*k+1)*x*(1+x)/(k+1 - x*(1+x)*(2*k+2)*(4*k+3)/(2*x*(1+x)*(4*k+3) + (2*k+3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013 a(n) ~ sqrt(2-sqrt(2))*2^(n-1/2)*(1+sqrt(2))^(n-1)/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Jun 29 2013 a(n+1) = sum_{k=0..floor(n/2)}A085880(n-k,k). - Philippe Deléham, Nov 15 2013 MAPLE spec := [S, {C=Prod(B, Z), S=Union(B, C, Z), B=Prod(S, S)}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20); MATHEMATICA InverseSeries[Series[(y-y^2)/(1+y^2), {y, 0, 24}], x] (* then A(x)= y(x) *) (* Len Smiley, Apr 12 2000 *) CoefficientList[Series[(1 - Sqrt[1 - 4 x - 4 x^2]) / (2(1 + x)), {x, 0, 33}], x] (* Vincenzo Librandi, Feb 12 2016 *) PROG (PARI) a(n)=polcoeff((1-sqrt(1-4*x*(1+x+O(x^n))))/2/(1+x), n) CROSSREFS A025227(n)=a(n)+a(n-1). Diagonal entries of A071943 and A071945. Sequence in context: A276549 A049188 A049165 * A049179 A049154 A225305 Adjacent sequences:  A052706 A052707 A052708 * A052710 A052711 A052712 KEYWORD easy,nonn AUTHOR encyclopedia(AT)pommard.inria.fr, Jan 25 2000 EXTENSIONS Better g.f. and recurrence from Michael Somos, Aug 03 2000 More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000 STATUS approved

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

Last modified June 20 11:38 EDT 2019. Contains 324234 sequences. (Running on oeis4.)