A135337 -id:A135337 - cp's OEIS frontend

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

N. J. A. Sloane, Feb 12 2001

nonn

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)

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

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.

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

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

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

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

x='x+O('x^66); Vec( 2/(2-3*x+x*(1-4*x)^(1/2)) ) \\ Joerg Arndt, Oct 02 2013

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

A135331 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k DUUU's starting at level 1.

Original entry on oeis.org

1, 1, 2, 5, 13, 1, 36, 6, 105, 27, 320, 108, 1, 1011, 409, 10, 3289, 1508, 65, 10957, 5491, 347, 1, 37216, 19898, 1658, 14, 128435, 72063, 7395, 119, 449142, 261436, 31527, 794, 1, 1588228, 951258, 130353, 4583, 18

Offset: 0

N. J. A. Sloane, Dec 07 2007

The formula for T(n,k)=l_{n,k} in the reference (p. 2919) does not appear to work (a typo is possible). - Emeric Deutsch, Dec 14 2007

Row 0 has 1 term; row n (n>=1) has floor((n+2)/3) terms. Row sums are the Catalan numbers (A000108). Column 0 yields A135337. - Emeric Deutsch, Dec 14 2007

			Triangle begins:
1
1
2
5
13 1
36 6
105 27
320 108 1
1011 409 10
3289 1508 65
10957 5491 347 1
...
T(5,1)=6 because we have U(DUUU)UDDDD, U(DUUU)DUDDD, U(DUUU)DDUDD, U(DUUU)DDDUD, UDU(DUUU)DDD and UUD(DUUU)DDD (the DUUU's starting at level 1 are shown between parentheses).

A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.

Cf. A000108, A135337.

G:=1+z*C^2/(1+(1-t)*z^3*C^4): C:=((1-sqrt(1-4*z))*1/2)/z: Gser:=simplify(series(G,z=0,16)): for n from 0 to 14 do P[n]:=sort(coeff(Gser,z,n)) end do: 1; for n from 0 to 14 do seq(coeff(P[n],t,j),j=0..floor((n-1)*1/3)) end do; # yields sequence in triangular form; Emeric Deutsch, Dec 14 2007

G.f.: G(t,z)=1+zC^2/[1+(1-t)z^3*C^4], where C=[1-sqrt(1-4z)]/(2z) is the g.f. of the Catalan numbers (A000108). - Emeric Deutsch, Dec 14 2007

More terms from Emeric Deutsch, Dec 14 2007

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Formula