A166300 Number of Dyck paths of semilength n, having no ascents and no descents of length 1, and having no UUDD's starting at level 0.

1, 0, 0, 1, 1, 2, 5, 10, 22, 50, 113, 260, 605, 1418, 3350, 7967, 19055, 45810, 110637, 268301, 653066, 1594980, 3907395, 9599326, 23643751, 58374972, 144442170, 358136905, 889671937, 2214015802, 5518884019, 13778312440, 34448765740

Offset: 0

Author

Emeric Deutsch, Nov 07 2009

Keywords

• nonn

Comments

a(n) = A166299(n,0).

a(n) is the number of peakless Motzkin paths of length n with no (1,0)-steps at level 0. Example: a(5)=2 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have UHHHD and UUHDD. - Emeric Deutsch, May 03 2011

From Paul Barry, Mar 31 2011: (Start)

The Hankel transform of a(n+3) is A188444(n+1).

a(n+3) gives the diagonal sums of the triangle A100754.

a(n+3) has g.f. 1/(1-x-x^2/(1-2x+3x^2/(1+2x+x^2/(1-2x-(1/3)x^2/(1-x-(2/3)x^2/(1-2x+(5/2)x^2/(1+2x+(3/2)x^2/(1-...)))))))) (continued fraction) where the coefficients of x^2 have denominators A188442 and numerators A188443. (End)

The Ca1 triangle sums of triangle A175136 lead to this sequence (n>=3). For the definitions of the Ca1 and other triangle sums see A180662. - Johannes W. Meijer, May 06 2011

a(n) is the number of closed Deutsch paths of n steps with all peaks at even height. A Deutsch path is a lattice path of up-steps (1,1) and down-steps (1,-j), j>=1, starting at the origin that never goes below the x-axis, and it is closed if it ends on the x-axis. For example a(5) = 2 counts UUUU4, UU1U2, where U denotes an up-step and a down-step is denoted by its length, and a(6) = 5 counts UUUU13, UUUU22, UUUU31, UU1U11, UU2UU2. - David Callan, Dec 08 2021

Examples

			a(5)=2 because we have UUUDDUUDDD and UUUUUDDDDD.
G.f. = 1 + x^3 + x^4 + 2*x^5 + 5*x^6 + 10*x^7 + 22*x^8 + 50*x^9 + 113*x^10 + ...
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Jean Luc Baril, Rigoberto Flórez, and José L. Ramirez, Generalized Narayana arrays, restricted Dyck paths, and related bijections, Univ. Bourgogne (France, 2025). See p. 22.

Crossrefs

Cf. A166299, A180662, A188442, A188443, A188444.

Programs

Magma

m:=40; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!(2/(1+x+x^2+Sqrt((1+x+x^2)*(1-3*x+x^2))))); // G. C. Greubel, Sep 22 2018

Maple

G := 2/(1+z+z^2+sqrt((1+z+z^2)*(1-3*z+z^2))): Gser := series(G, z = 0, 35): seq(coeff(Gser, z, n), n = 0 .. 32);

Mathematica

CoefficientList[Series[2/(1+x+x^2+Sqrt[(1+x+x^2)*(1-3*x+x^2)]), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 12 2014 *)

Maxima

a(n):=sum((j+1)*sum((binomial(j+2*i+1,i)*sum(binomial(k,n-k-j-2*i)*binomial(k+j+2*i,k)*(-1)^(n-k),k,0,n-j-2*i))/(j+2*i+1),i,0,n-j),j,0,n); /*  Vladimir Kruchinin, Mar 07 2016 */

PARI

{a(n) = local(A); A = 1 + O(x); for( k=1, ceil(n / 5), A = 1 / (1 - x^3 / (1 - x / (1 - x * A)))); polcoeff( A, n)}; /* Michael Somos, May 12 2012 */

PARI

x='x+O('x^40); Vec(2/(1+x+x^2+((1+x+x^2)*(1-3*x+x^2))^(1/2))) \\ Altug Alkan, Sep 23 2018

Formula

G.f. = G(z)=2/(1 + z + z^2 + sqrt((1 + z + z^2)*(1 - 3*z + z^2))).

G.f.: 1 / (1 - x^3 / (1 - x / (1 - x / (1 - x^3 / (1 - x / (1 - x / ...)))))). - Michael Somos, May 12 2012

G.f. A(x) satisfies A(x) = 1 / (1 - x^3 / (1 - x / (1 - x *A(x)))). - Michael Somos, May 12 2012

Conjecture: (n+1)*a(n) +2*(-n+1)*a(n-1) +(-n+1)*a(n-2) +2*(-n+1)*a(n-3) +(n-3)*a(n-4)=0. - R. J. Mathar, Nov 24 2012

a(n) ~ (3+sqrt(5))^(n+2) * sqrt(7*sqrt(5)-15) / (2 * sqrt(Pi) * n^(3/2) * 2^(n+9/2)). - Vaclav Kotesovec, Feb 12 2014. Equivalently, a(n) ~ 5^(1/4) * phi^(2*n + 2) / (8 * sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021

a(n) = Sum_{j=0..n}((j+1)*Sum_{i=0..n-j}((binomial(j+2*i+1,i)*Sum_{k=0..n-j-2*i}(binomial(k,n-k-j-2*i)*binomial(k+j+2*i,k)*(-1)^(n-k)))/(j+2*i+1))). - Vladimir Kruchinin, Mar 07 2016