A152172 a(n) is the number of Dyck paths of semilength n without height of peaks 0 (mod 3) and height of valleys 1 (mod 3).

1, 1, 2, 3, 6, 12, 26, 59, 138, 332, 814, 2028, 5118, 13054, 33598, 87143, 227542, 597640, 1577866, 4185108, 11146570, 29798682, 79932298, 215072896, 580327122, 1569942098, 4257254850, 11569980794, 31508150890, 85968266198, 234975421554, 643317390627

Offset: 0

Author

Jun Ma (majun(AT)math.sinica.edu.tw), Nov 27 2008

Keywords

• nonn

Comments

Hankel transform gives A328380(n+1). - Thomas Scheuerle, Oct 23 2024

Links

• Shu-Chung Liu, Jun Ma, Yeong-Nan Yeh, Dyck Paths with Peak- and Valley-Avoiding Sets, Stud. Appl Math. 121 (3) (2008) 263-289.

Crossrefs

Almost the same as A086625. - R. J. Mathar, Dec 03 2008

Cf. A000108, A328380.

Programs

Maple

b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0, `if`(x=0, 1,
      `if`(t=0 and irem(y, 3)=0, 0, b(x-1, y-1, 1))+
      `if`(t=1 and irem(y, 3)=1, 0, b(x-1, y+1, 0))))
    end:
a:= n-> b(2*n, 0$2):
seq(a(n), n=0..35);  # Alois P. Heinz, Oct 23 2024

Mathematica

CoefficientList[Series[(1+x-2x^2-Sqrt[1-2x-3x^2+4x^4])/(2(1-x)x), {x, 0, 30}], x] (* Harvey P. Dale, Apr 10 2012 *)

PARI

{a(n) = my(A, E=ellinit([1, -1, 0, -1, 1]),b=1,c=1,v=[1]); if( n<0, 0, A = O(x); for(k=1, n, v=concat(v,(1/b)*(1/c)); b=(1/b)*(1/c); c=(1-ellmul(E,[0,1],2*k+1)[1])/b; v=concat(v,c) ); for(k=1, #v,A = 1 /(1 - v[#v+1-k]*x*A));polcoeff(A, n))}; \\ Thomas Scheuerle, Oct 23 2024

PARI

{a(n) = my(A,v=[1,1,-1,-1,3]); if( n<0, 0, A = O(x); for(k=1, n+1, v=concat(v,(1/v[#v])*(1/v[#v-1])); v=concat(v,(v[#v-2]*v[#v-1]-2)/(v[#v-4]*v[#v-3]*v[#v-2]^2*v[#v-1]^2*v[#v]))); for(k=1, #v,A = 1 /(1 - v[#v+1-k]*x*A));polcoeff(A, n))} \\ Thomas Scheuerle, Oct 23 2024

Formula

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

(n+1)*a(n) - 2*n*a(n-1) + (7-3*n)*a(n-2) + 4*a(n-3) + 4*(n-4)*a(n-4) = 0 for n>=4. - R. J. Mathar, Aug 14 2012

G.f.: 1 - 1/G(0) where G(k) = 1 - 1/(x + x^2/(1 + x/G(k+1) )); (continued fraction, 3-step). - Sergei N. Gladkovskii, Nov 28 2012

G.f.: 1/(1-x/(1-b_{0}*x/(1-c_{0}*x/(1-b_{1}*x/(1-c_{1}*x/(...)))))), with (1-b_{n}*c_{n}) = the x-coordinate of (2*n+1) times the point [0, 1] under the group law of the elliptic curve y^2 + x*y = x^3 - x^2 - x+1. b_{n} = (1/b_{n-1})*(1/c_{n-1}) with b_{0} = 1, also c_{n} = (c_{n-1}*b_{n-1} - 2)/(b_{n}*c_{n-2}*b_{n-2}*(c_{n-1}*b_{n-1})^2) - Thomas Scheuerle, Oct 23 2024