login
A347147
Square array read by antidiagonals: T(n,k) is the number of rook paths from (1,1) to (n,k) if the rook may travel 1 to i squares along rank or file i, n >= 1, k >= 1.
1
1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 7, 10, 7, 1, 1, 12, 23, 23, 12, 1, 1, 20, 50, 62, 50, 20, 1, 1, 33, 104, 156, 156, 104, 33, 1, 1, 54, 211, 373, 438, 373, 211, 54, 1, 1, 88, 420, 859, 1155, 1155, 859, 420, 88, 1, 1, 143, 824, 1925, 2915, 3306, 2915, 1925, 824, 143, 1
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
Cf. A000071 (row n=2, and column k=2).
Cf. A035002 (unlimited rook moves).
A347148 gives a similar array that includes the 0 file and rank.
Sequence in context: A361745 A296157 A113582 * A295213 A118245 A104382
KEYWORD
nonn,tabl
AUTHOR
Glen Whitney, Aug 20 2021
STATUS
approved