A143955 Sum of the altitudes of the leftmost valleys of all Dyck paths of semilength n (if path has no valley, then this altitude is taken to be 0).

0, 0, 0, 1, 6, 26, 101, 376, 1377, 5017, 18277, 66727, 244377, 898129, 3312554, 12260129, 45526754, 169588754, 633580634, 2373550184, 8914719134, 33562602134, 126640791884, 478848661898, 1814142235028, 6885560250148

Offset: 0

Author

Emeric Deutsch, Oct 14 2008

Keywords

• nonn

Comments

The positive terms form the partial sums of A000344.

Examples

			a(4)=6 because the Dyck paths of semilength 4 with leftmost valley at a positive altitude are UUDUDDUD, UUDUDUDD, UUDUUDDD, UUUDDUDD and UUUDUDDD, where U=(1,1) and D=(1,-1); these altitudes are 1, 1, 1, 1 and 2, respectively.
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..200

Crossrefs

Cf. A000108, A000344, A097607, A323224.

Programs

Maple

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

Mathematica

CoefficientList[Series[x^3 ((1 - (1 - 4 x)^(1/2))/(2 x))^5/(1 - x), {x, 0, 40}], x] (* Vaclav Kotesovec, Mar 21 2014 *)

Maxima

a(n):=5*sum(binomial(2*k,k-2)/(k+3),k,2,n-1); /* Vladimir Kruchinin, Mar 15 2016 */

Python

from functools import cache
@cache
def B(n, k):
    if n <= 0 or k <= 0: return 0
    if n == k: return 1
    return B(n - 1, k) + B(n, k - 1)
def A143955(k):
    return B(k + 3, k - 2)
print([A143955(n) for n in range(26)]) # Peter Luschny, May 15 2022

Formula

a(n) = Sum_{k>=0} k*A097607(n,k).

G.f.: z^3*C^5/(1-z), where C=(1-sqrt(1-4*z))/(2*z) is the generating function of the Catalan numbers (A000108).

Conjecture: (n+2)*a(n) -4*(2*n+1)*a(n-1) +2*(10*n-9)*a(n-2) +17*(2-n)*a(n-3) +2*(2*n-7)*a(n-4)=0. - R. J. Mathar, Jul 24 2012

a(n) ~ 5*4^n/(3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Mar 21 2014

a(n) = 5*Sum_{k=2..n-1}(binomial(2*k,k-2)/(k+3)). - Vladimir Kruchinin, Mar 15 2016