A052709 Expansion of g.f. (1-sqrt(1-4*x-4*x^2))/(2*(1+x)).

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

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• easy
• nonn

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.

Crossrefs

Diagonal entries of A071943 and A071945.

Cf. A000108, A000670, A025227, A052709, A056986, A071943, A085880.

Cf. A102726, A117434, A158005, A226316, A333217, A335479.

Programs

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

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 *)

PARI

a(n)=polcoeff((1-sqrt(1-4*x*(1+x+O(x^n))))/2/(1+x),n)

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

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

Extensions

Better g.f. and recurrence from Michael Somos, Aug 03 2000

More terms from Larry Reeves (larryr(AT)acm.org), Oct 03 2000