A262600 Number of Dyck paths of semilength n and height exactly 4.

0, 0, 0, 0, 1, 7, 33, 132, 484, 1684, 5661, 18579, 59917, 190696, 600744, 1877256, 5828185, 17998783, 55342617, 169552428, 517884748, 1577812060, 4796682165, 14555626635, 44100374341, 133436026192, 403279293648, 1217616622992, 3673214880049, 11072960931319

Offset

0,6

Links

Colin Barker, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (7,-16,13,-3).

Formula

a(n) = A124302(n) - A001519(n).

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

a(n) = A080936(n,4).

From Colin Barker, Feb 08 2016: (Start)

a(n) = 7*a(n-1)-16*a(n-2)+13*a(n-3)-3*a(n-4) for n>4.

a(n) = 2^(-1-n)*(5*2^n*(3+3^n)+3*(-5+sqrt(5))*(3+sqrt(5))^n-3*(3-sqrt(5))^n*(5+sqrt(5)))/15 for n>0. (End)

E.g.f.: (2 + 3*exp(x) + exp(3*x))/6 - exp(3*x/2)*(5*cosh(sqrt(5)*x/2) - sqrt(5)*sinh(sqrt(5)*x/2))/5. - Stefano Spezia, May 21 2024

Example

a(4) = 1 because the only favorable path is UUUUDDDD.

Mathematica

CoefficientList[ Series[x^4/((x-1) (3 x-1) (x^2-3 x+1)), {x, 0, 30}], x].

Prog

(PARI) a(n) = if( n<1, n==0, (3^(n-1) + 1) / 2) - fibonacci(2*n-1); vector(30, n, a(n-1)) \\ Altug Alkan, Sep 25 2015
(Magma) [((3^(n-1)+1)/2)-Fibonacci(2*n-1): n in [1.. 35]]; // Vincenzo Librandi, Sep 26 2015
(PARI) concat(vector(4), Vec(x^4/((1-x)*(1-3*x)*(1-3*x+x^2)) + O(x^100))) \\ Colin Barker, Feb 08 2016

Crossrefs

Cf. A001519, A124302.

Column k=4 of A080936.

Sequence in context: A258458 A320546 A066810 * A034577 A372878 A141291

Adjacent sequences: A262597 A262598 A262599 * A262601 A262602 A262603

Keyword

nonn,easy

Author

Ran Pan, Sep 25 2015

Status

approved