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, 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

Table of n, a(n) for n=1..66.

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

Adjacent sequences: A347144 A347145 A347146 * A347148 A347149 A347150

Keyword

nonn,tabl

Author

Glen Whitney, Aug 20 2021

Status

approved