A035929 Number of Dyck n-paths starting U^mD^m (an m-pyramid), followed by a pyramid-free Dyck path.

0, 1, 1, 1, 2, 6, 19, 61, 200, 670, 2286, 7918, 27770, 98424, 351983, 1268541, 4602752, 16799894, 61642078, 227239086, 841230292, 3126039364, 11656497518, 43601626146, 163561902392, 615183356156, 2319423532024, 8764535189296, 33187922345210, 125912855167740

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Hankel transform is -A128834. - Paul Barry, Jul 04 2009

Examples

			The a(5) = 6 cases are UUUUUDDDDD, UDUUUDUDDD, UDUUUDDUDD, UDUUDUUDDDD, UDUUDUDUDUDD and UUDDUUDUDD.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..500
• J.-L. Baril, S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016.
• Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
• W. Kuszmaul, Fast Algorithms for Finding Pattern Avoiders and Counting Pattern Occurrences in Permutations, arXiv:1509.08216 [cs.DM], 2015.
• Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Crossrefs

Cf. A082989.

Programs

Magma

/* Expansion */ Q:=Rationals(); R:=PowerSeriesRing(Q,30); R!(2*x/(1+x+(1-x)*Sqrt(1-4*x))); // G. C. Greubel, Jan 15 2018

Maple

A:= proc(n) option remember; if n=0 then 0 else convert (series ((A(n-1)^2 *(x^2-2*x+2) +x)/ (x+1), x,n+1), polynom) fi end: a:= n-> coeff (A(n), x,n): seq (a(n), n=0..25); # Alois P. Heinz, Aug 23 2008

Mathematica

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

PARI

x='x+O('x^30); concat([0], Vec(2*x/(1+x+(1-x)*sqrt(1-4*x)))) \\ G. C. Greubel, Jan 15 2018

Formula

G.f.: A(x) satisfies A^2*(x^2-2*x+2) - A*(x+1) + x = 0.

The generating function can be written as x/(1-x) times that of A082989.

G.f.: (2*x)/(1+x+(1-x)*sqrt(1-4*x)) = 1/(1-x(1-x)/(1-x/(1-x/(1-x/(1-x/(1-x/(1-... (continued fraction). - Paul Barry, Jul 04 2009

From Gary W. Adamson, Jul 14 2011: (Start)

a(n), n>0; is the upper left term in M^(n-1), where M is the infinite square production matrix:

1, 1, 0, 0, 0, 0, ...

0, 1, 1, 0, 0, 0, ...

1, 1, 1, 1, 0, 0, ...

1, 1, 1, 1, 1, 0, ...

1, 1, 1, 1, 1, 1, ...

... (End)

D-finite with recurrence: 2*n*a(n) +4*(-3*n+4)*a(n-1) +(19*n-44)*a(n-2) + (-13*n + 36)*a(n-3) +2*(2*n-7)*a(n-4)=0. - R. J. Mathar, Nov 24 2012

a(n) ~ 3 * 4^n / (25 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Feb 12 2014

From Alexander Burstein, Aug 05 2017: (Start)

G.f: A = x/(1-(1-x)*x*C) = x*C/(1+x^2*C^2) = x*C^3/(1+2*x*C^3), where C is the g.f. of A000108.

A/x composed with x*C = g.f. of A165543, where A and C are as above. (End)

Extensions

Edited by Louis Shapiro, Feb 16 2005

Wrong g.f. removed by Vaclav Kotesovec, Feb 12 2014