The OEIS is supported by the many generous donors to the OEIS Foundation.

 Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 60th year, we have over 367,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”). Other ways to Give
 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A052709 Expansion of g.f. (1-sqrt(1-4*x-4*x^2))/(2*(1+x)). 42
 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, 127100310290431, 578433619525633, 2638370120138751 (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 From Gus Wiseman, Jun 17 2021: (Start) Conjecture: For n > 0, also the number of sequences of length n - 1 covering an initial interval of positive integers and avoiding three terms (..., x, ..., y, ..., z, ...) such that x <= y <= z. The version avoiding the strict pattern (1,2,3) is A226316. Sequences covering an initial interval are counted by A000670. The a(1) = 1 through a(4) = 9 sequences are: () (1) (1,1) (1,2,1) (1,2) (1,3,2) (2,1) (2,1,1) (2,1,2) (2,1,3) (2,2,1) (2,3,1) (3,1,2) (3,2,1) (End) LINKS N. J. A. Sloane, Table of n, a(n) for n = 0..499 Marilena Barnabei, Flavio Bonetti, Niccolò Castronuovo, and 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. Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020. Daniel Birmajer, Juan B. Gil, David S. Kenepp, and Michael D. Weiner, Restricted generating trees for weak orderings, arXiv:2108.04302 [math.CO], 2021. Daniel Birmajer, Juan B. Gil, Peter R. W. McNamara, and 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, and 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 and 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) + a(n-1) = A025227(n). a(n) = Sum_{k=0..floor((n-1)/2)} (2*n-2-2*k)!/(k!*(n-k)!*(n-1-2*k)!). - Emeric Deutsch, Nov 14 2001 D-finite with recurrence: 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} Catalan(k)*binomial(k, n-k). - Paul Barry, Feb 22 2005 From Paul Barry, Mar 14 2006: (Start) G.f. is x*c(x*(1+x)) where c(x) is the g.f. of A000108. Row sums of A117434. (End) a(n+1) = (1/(2*Pi))*Integral_{x=2-2*sqrt(2)..2+2*sqrt(2)} x^n*(4+4x-x^2)/(2*(1+x)). - Paul Barry, Apr 01 2007 From Gary W. Adamson, Jul 22 2011: (Start) For n>0, a(n) is the upper left term in M^(n-1), where M is 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, ... ... (End) 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 -4x -4x^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) (Magma) [0] cat [(&+[Binomial(n, k+1)*Binomial(2*k, n-1): k in [0..n-1]])/n: n in [1..30]]; // G. C. Greubel, May 30 2022 (SageMath) [sum(binomial(k, n-k-1)*catalan_number(k) for k in (0..n-1)) for n in (0..30)] # G. C. Greubel, May 30 2022 CROSSREFS Diagonal entries of A071943 and A071945. Cf. A000108, A000670, A025227, A052709, A056986, A071943, A085880. Cf. A102726, A117434, A158005, A226316, A333217, A335479. 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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 9 09:12 EST 2023. Contains 367690 sequences. (Running on oeis4.)