A059019 Number of Dyck paths of semilength n with no peak at height 3.

1, 1, 2, 4, 9, 22, 58, 163, 483, 1494, 4783, 15740, 52956, 181391, 630533, 2218761, 7888266, 28291588, 102237141, 371884771, 1360527143, 5002837936, 18479695171, 68539149518, 255137783916, 952914971191, 3569834343547, 13410481705795

Offset

0,3

Comments

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

a(n) is the upper left term in M^n, where M is an infinite square production matrix in which a column of (1,1,0,0,0,...) is prepended to an infinite lower triangular matrix of all 1's and the rest zeros, as follows:

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

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

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

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

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

... (End)

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]

Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.

P. Peart and W.-J. Woan, Dyck Paths With No Peaks at Height k, J. Integer Sequences, 4 (2001), #01.1.3.

Formula

G.f.: 2/(2 - 3*x + x*(1-4*x)^(1/2)).

a(n) = Sum_{k=1..n-1} (Sum_{j=0..min(k,n-k)} binomial(k,j)*j*binomial(2*n-2*k-j-1, n-k-j) /(n-k)) + 1. - Vladimir Kruchinin, Oct 02 2013

a(n) ~ 2^(2*n + 2)/(25*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Dec 10 2013

a(n+1) - a(n) = A135337(n), n > 0. - Philippe Deléham, Oct 02 2014

Example

1 + x + 2*x^2 + 4*x^3 + 9*x^4 + 22*x^5 + 58*x^6 + ...

Maple

A059019:=n->add(add(binomial(k, j)*j*binomial(2*n-2*k-j-1, n-k-j)/(n-k), j=0..min(k, n-k)), k=1..n-1)+1: seq(A059019(n), n=0..30); # Wesley Ivan Hurt, Oct 01 2014

Mathematica

CoefficientList[Series[2/(2-3*x+x*Sqrt[1-4*x]), {x, 0, 20}], x]

Prog

(Maxima)
a(n):=sum(sum(binomial(k, j)*j*binomial(2*n-2*k-j-1, n-k-j), j, 0, min(k, n-k))/(n-k), k, 1, n-1)+1; \\ Vladimir Kruchinin, Oct 02 2013
(PARI) x='x+O('x^66); Vec( 2/(2-3*x+x*(1-4*x)^(1/2)) ) \\ Joerg Arndt, Oct 02 2013

Crossrefs

G_1, G_2, G_3, G_4 give A000957, A000108, A059019, A059027, respectively.

Sequence in context: A124380 A176084 A192576 * A249560 A121953 A024427

Adjacent sequences: A059016 A059017 A059018 * A059020 A059021 A059022

Keyword

nonn

Author

N. J. A. Sloane, Feb 12 2001

Status

approved