|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
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.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|