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

1, 1, 5, 22, 117, 654, 3843, 22882, 137443, 827998, 4995443, 30155494, 182083275, 1099560942, 6640309323, 40101959542, 242184540139, 1462610652718, 8833070227499, 53345145429670, 322164911643723, 1945636121710110

Offset

0,3

Links

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

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 (6, 5, -24, -28, -6, 8).

Formula

G.f.: (1 - 5x - 6x^2 + 11x^3 + 12x^4 - 4x^5)/(1 - 6x - 5x^2 + 24x^3 + 28x^4 + 6x^5 - 8x^6). [corrected by Jean-François Alcover, Apr 02 2019]

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

b[n_, k_] := Boole[n >= 0 && k >= 0 && 0 <= n-k <= 6];
T[0, 0] = T[1, 1] = 1; T[n_, k_] /; b[n, k] == 1 := T[n, k] = b[n-1, k]* T[n-1, k] + b[n-2, k]*T[n-2, k] + b[n, k-1]*T[n, k-1] + b[n, k-2]*T[n, k-2]; T[_, _] = 0;
a[n_] := T[n, n];
Table[a[n], {n, 0, 21}]
(* or: *)
LinearRecurrence[{6, 5, -24, -28, -6, 8}, {1, 1, 5, 22, 117, 654}, 22] (* Jean-François Alcover, Apr 02 2019 *)

Crossrefs

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

Sequence in context: A005033 A127618 A127619 * A122951 A331836 A184181

Adjacent sequences: A127617 A127618 A127619 * A127621 A127622 A127623

Keyword

nonn,easy,walk

Author

Arvind Ayyer, Jan 20 2007

Status

approved