OFFSET
1,5
COMMENTS
Note that all of the rook moves are in the positive horizontal or vertical direction.
By symmetry, the array is equal to its transpose.
From the definition, T(1,1) = 1 and T(n,k) = Sum_{i=n-k..n-1} T(i,k) + Sum_{j=k-n..k-1} T(n,j) if we take T(n,k)=0 for n<=0 or k<=0.
LINKS
Alissa S. Crans and Glen T. Whitney, The Mathematical Playground: People and Problems from 31 Years of Math Horizons, AMS/MAA Problem Books (2024) Vol. 38. Problem 419, pp. 112-113.
FORMULA
T(n,k) = 2*(T(n-1,k)+T(n,k-1))-3T(n-1,k-1)-T(n,k-n-1)+T(n-1,k-n), for 1<n<k (can be shown by inclusion-exclusion on the paths); and symmetrically for 1<k<n.
T(n,n) = 2*(T(n-1,n)+T(n,n-1))-3T(n-1,n-1) = 4T(n-1,n)-3T(n-1,n-1), for n>1.
EXAMPLE
There are four rook paths with move length capped by the number of the rank or file it is moving along, from (1,1) to (3,2):
(1,1)->(2,1)->(3,1)->(3,2);
(1,1)->(2,1)->(2,2)->(3,2);
(1,1)->(1,2)->(2,2)->(3,2);
(1,1)->(1,2)->(3,2).
So T(3,2) = 4.
An initial portion of the full array:
n= 1 2 3 4 5 6 7 8 9 ...
-----------------------------------------
k=1: 1 1 1 1 1 1 1 1 1 ...
k=2: 1 2 4 7 12 20 33 54 88 ...
k=3: 1 4 10 23 50 104 211 420 824 ...
k=4: 1 7 23 62 156 373 859 1925 4226 ...
k=5: 1 12 50 156 438 1155 2915 7114 16917 ...
k=6: 1 20 104 373 1155 3306 8978 23450 59422 ...
....
PROG
(Python)
n = 1; k = 1;
T = [[], [0]] # Dummy 0th entry, and dummy [1][0]th entry.
T[n].append(1) # set T[1][1] to 1
print(f"T(1, 1) = {T[n][k]}")
for m in range(64):
if n == 1:
n = k + 1; k = 1;
T.append([0]); # initialize T[n], with dummy 0th entry.
else:
n -= 1; k += 1;
T[n].append(sum(T[i][k] for i in range(max(1, n-k), n))
+ sum(T[n][j] for j in range(max(1, k-n), k)))
print(f"T({n}, {k}) = {T[n][k]}")
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Glen Whitney, Aug 20 2021
STATUS
approved