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

Author

Glen Whitney, Aug 20 2021

Keywords

• nonn
• tabl

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.

Examples

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

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.

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.

Programs

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]}")

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

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.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.