A127617 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 3 with the steps (1,0), (0, 1), (2,0) and (0,2).
1, 1, 5, 22, 92, 395, 1684, 7189, 30685, 130973, 559038, 2386160, 10184931, 43472696, 185556025, 792015257, 3380586357, 14429474710, 61589830404, 262886022219, 1122085581740, 4789437042413, 20442921249973, 87257234103245, 372443097062686, 1589711867161816
Offset: 0
Examples
a(2)=5 because we can reach (2,2) in the following ways: (0,0),(1,0),(1,1),(2,1),(2,2) (0,0),(2,0),(2,2) (0,0),(1,0),(2,0),(2,2) (0,0),(2,0),(2,1),(2,2) (0,0),(1,0),(2,0),(2,1),(2,2)
Links
- Muniru A Asiru, Table of n, a(n) for n = 0..1550
- Arvind Ayyer and Doron Zeilberger, The Number of [Old-Time] Basketball games with Final Score n:n where the Home Team was never losing but also never ahead by more than w Points, arXiv:math/0610734 [math.CO], 2006-2007.
- Index entries for linear recurrences with constant coefficients, signature (3,5,2,-1).
Programs
-
Magma
I:=[1,1,5,22]; [n le 4 select I[n] else 3*Self(n-1)+5*Self(n-2)+2*Self(n-3)-Self(n-4): n in [1..30]]; // Vincenzo Librandi, Dec 13 2018
-
Maple
seq(coeff(series((1-2*x-3*x^2)/(1-3*x-5*x^2-2*x^3+x^4),x,n+1), x, n), n = 0 .. 25); # Muniru A Asiru, Dec 10 2018
-
Mathematica
LinearRecurrence[{3, 5, 2, -1}, {1, 1, 5, 22}, 23] (* Jean-François Alcover, Dec 10 2018 *) CoefficientList[Series[(1 - 2 x - 3 x^2) / (1 - 3 x - 5 x^2 - 2 x^3 + x^4), {x, 0, 33}], x] (* Vincenzo Librandi, Dec 13 2018 *) b[n_, k_] := Boole[n >= 0 && k >= 0 && 0 <= n-k <= 3]; T[0, 0] = T[1, 1] = 1; T[n_, k_] /; b[n, k] == 1 := T[n, k] = b[n-2, k]* T[n-2, k] + b[n-1, k]*T[n-1, k] + b[n, k-2]*T[n, k-2] + b[n, k-1]*T[n, k-1]; T[, ] = 0; a[n_] := T[n, n]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Apr 03 2019 *)
Formula
G.f.: (1 - 2*x - 3*x^2) / (1 - 3*x - 5*x^2 - 2*x^3 + x^4).
a(n) = 3*a(n-1)+5*a(n-2)+2*a(n-3)-a(n-4). - Vincenzo Librandi, Dec 13 2018