A127618 Number of walks from (0,0) to (n,n) in the region 0 <= x-y <= 4 with the steps (1,0), (0, 1), (2,0) and (0,2).

1, 1, 5, 22, 117, 590, 3018, 15378, 78440, 399992, 2039852, 10402480, 53049048, 270531368, 1379614800, 7035549312, 35878823312, 182969359520, 933079279328, 4758375627808, 24266039468160, 123748253080832, 631072497876672

Offset

0,3

Links

Table of n, a(n) for n=0..22.

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 (4,6,-2).

Formula

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

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)

Mathematica

Join[{1, 1}, LinearRecurrence[{4, 6, -2}, {5, 22, 117}, 21]] (* Jean-François Alcover, Dec 10 2018 *)
b[n_, k_] := Boole[n >= 0 && k >= 0 && 0 <= n-k <= 4];
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, 22}] (* Jean-François Alcover, Apr 03 2019 *)

Crossrefs

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

Sequence in context: A213167 A355398 A005033 * A127619 A127620 A122951

Adjacent sequences: A127615 A127616 A127617 * A127619 A127620 A127621

Keyword

nonn,easy,walk

Author

Arvind Ayyer, Jan 20 2007

Status

approved