OFFSET
0,4
COMMENTS
Number of underdiagonal paths from (0,0) to the line x=n-2, using only steps R=(1,0), V=(0,1) and D=(2,1). E.g., a(4)=7 because we have RR, RRV, RVR, D, RVRV, RRVV and DV. - Emeric Deutsch, Dec 21 2003
LINKS
Muniru A Asiru, Table of n, a(n) for n = 0..1000
Kassie Archer and Robert P. Laudone, Arrow pattern avoidance in permutations: structure and enumeration, arXiv:2603.04218 [math.CO], 2026. See p. 15.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 660
Cyril Banderier and Donnatella Merlini, Lattice paths with an infinite set of jumps, FPSAC02, Melbourne, 2002.
Donatella Merlini, Douglas G. Rogers, Renzo Sprugnoli, and M. Cecilia Verri, On some alternative characterizations of Riordan arrays, Can. J. Math., 49 (2) (1997) 301-310.
FORMULA
D-finite with recurrence: a(1)=0, a(2)=1, a(3)=2, 4*(n+1)*a(n) + (10+8*n)*a(n+1) + (2+3*n)*a(n+2) + (-n-3)*a(n+3) = 0.
a(n+2) = Sum_{k=0..n} Sum_{j=0..n} C(j,n-j)*A001263(j,k). - Paul Barry, Jun 30 2009
a(n) = Sum_{j=1..floor(n/2)} C(2*n-2*j,n)*C(n,j-1)/(n-j). - Vladimir Kruchinin, Jan 16 2015
G.f.: A(x) satisfies A(x) = C(x*(1+A(x)))^2, where x*C(x) is g.f. of Catalan numbers. - Vladimir Kruchinin, Jan 16 2015
a(n) = C(2*n-2,n)*3F2((2-n)/2,(3-n)/2,-n;3/2-n,2-n;-1)/(n-1), n>1. - Benedict W. J. Irwin, Sep 13 2016
a(n) ~ 2^(n + 3/4) * (1 + sqrt(2))^(n - 5/2) / (sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Sep 03 2019
MAPLE
spec := [S, {S=Prod(B, B), C=Prod(S, Z), B=Union(S, C, Z)}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
MATHEMATICA
CoefficientList[Series[(2x^2)/(1-2x-2x^2+Sqrt[1-4x-4x^2]), {x, 0, 30}], x] (* Harvey P. Dale, Dec 16 2014 *)
Join[{0, 0}, Table[(Binomial[2(m-1), m]HypergeometricPFQ[{(2-m)/2, (3-m)/2, -m}, {3/2-m, 2-m}, -1])/(m-1), {m, 2, 20}]] (* Benedict W. J. Irwin, Sep 13 2016 *)
PROG
(Maxima)
a(n):=(sum(binomial(2*n-2*j, n)*binomial(n, j-1)/(n-j), j, 1, n/2)); /* Vladimir Kruchinin, Jan 16 2015 */
CROSSREFS
KEYWORD
easy,nonn
AUTHOR
INRIA Encyclopedia of Combinatorial Structures, Jan 25 2000
EXTENSIONS
More terms from Emeric Deutsch, Mar 07 2004
STATUS
approved