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

Author

Arvind Ayyer, Jan 20 2007

Keywords

• nonn
• easy
• walk

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

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

Crossrefs

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

Programs

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

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]