login
A059019
Number of Dyck paths of semilength n with no peak at height 3.
4
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
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
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Feb 12 2001
STATUS
approved