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,3

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).

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

Example

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)

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 *)

Prog

(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

Crossrefs

Cf. A000108, A046717, A122951, A127618, A127619, A127620.

Sequence in context: A071715 A278472 A010036 * A095932 A000346 A289798

Adjacent sequences: A127614 A127615 A127616 * A127618 A127619 A127620

Keyword

nonn,easy,walk

Author

Arvind Ayyer, Jan 20 2007

Status

approved