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
Examples
a(4) = 1 because the only favorable path is UUUUDDDD.
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).
Programs
-
Magma
[((3^(n-1)+1)/2)-Fibonacci(2*n-1): n in [1.. 35]]; // Vincenzo Librandi, Sep 26 2015
-
Mathematica
CoefficientList[ Series[x^4/((x-1) (3 x-1) (x^2-3 x+1)), {x, 0, 30}], x] -
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
-
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
Formula
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