login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A052709 Expansion of (1-sqrt(1-4x-4x^2))/(2(1+x)). 22
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

REFERENCES

P Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, 491 (2016) 343-385.

Xiang-Ke Chang, XB Hu, H Lei, YN Yeh, Combinatorial proofs of addition formulas, The Electronic Journal of Combinatorics, 23(1) (2016), #P1.8.

LINKS

N. J. A. Sloane, Table of n, a(n) for n = 0..499

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.

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.

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 13 09:05 EST 2017. Contains 295957 sequences.