login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

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

%I #15 Apr 03 2019 08:01:29

%S 1,1,5,22,117,654,3674,20763,117349,663529,3751874,21215245,119963514,

%T 678345474,3835772387,21689760681,122646936325,693519457822,

%U 3921575652821,22174944672838,125390459051898,709032985366923

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

%H Arvind Ayyer and Doron Zeilberger, <a href="https://arxiv.org/abs/math/0610734">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</a>, arXiv:math/0610734 [math.CO], 2006-2007.

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5, 6, -11, -12, 4).

%F G.f.: (1-4x-6x^2+2x^3)/(1-5x-6x^2+11x^3+12x^4-4x^5). [Typo corrected by _Jean-François Alcover_, Dec 10 2018]

%e a(2)=5 because we can reach (2,2) in the following ways:

%e (0,0),(1,0),(1,1),(2,1),(2,2)

%e (0,0),(2,0),(2,2)

%e (0,0),(1,0),(2,0),(2,2)

%e (0,0),(2,0),(2,1),(2,2)

%e (0,0),(1,0),(2,0),(2,1),(2,2)

%t LinearRecurrence[{5, 6, -11, -12, 4}, {1, 1, 5, 22, 117}, 22] (* _Jean-François Alcover_, Dec 10 2018 *)

%t b[n_, k_] := Boole[n >= 0 && k >= 0 && 0 <= n - k <= 5];

%t 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;

%t a[n_] := T[n, n];

%t Table[a[n], {n, 0, 21}] (* _Jean-François Alcover_, Apr 03 2019 *)

%Y Cf. A000108, A046717, A122951, A127617, A127618, A127620.

%K nonn,easy,walk

%O 0,3

%A _Arvind Ayyer_, Jan 20 2007