A347148 Square array read by antidiagonals: T(n,0) = T(0,k) = 1 and for n > 0, k > 0, T(n,k) = Sum_{i=1..min(n,k)} (T(n-i,k) + T(n,k-i)).

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 8, 4, 1, 1, 5, 16, 16, 5, 1, 1, 6, 30, 42, 30, 6, 1, 1, 7, 53, 98, 98, 53, 7, 1, 1, 8, 91, 216, 268, 216, 91, 8, 1, 1, 9, 153, 455, 677, 677, 455, 153, 9, 1, 1, 10, 254, 931, 1627, 1906, 1627, 931, 254, 10, 1

Offset: 1

Author

Glen Whitney, Aug 21 2021

Keywords

• nonn
• tabl

Comments

From the definition, this is the number of ways a rook can get to square (n,k) if it is allowed to enter at any square (n,0) or (0,k), and can proceed 1 to i squares to the right along rank i or up file i at each move thereafter.

By symmetry, the array is equal to its transpose.

In its triangular form produced by "rotating the array an eighth turn", it is generated by a recurrence that can be stated as "each entry is the sum of the largest symmetric V of entries that converge at the given location" (see the triangle in Examples).

Examples

			Initial values of T:
  T(1,1) = T(1,0) + T(0,1) = 2,
  T(2,1) = T(1,1) + T(2,0) = 3 = T(1,2),
  T(3,1) = T(2,1) + T(3,0) = 4,
  T(2,2) = T(1,2) + T(2,1) + T(0,2) + T(2,0) = 8,
  T(3,2) = T(2,2) + T(3,1) + T(1,2) + T(3,0) = 16.
An initial portion of the full array:
    n=  0 1  2   3   4    5    6     7     8 ...
       --------------------------------------
  k=0:  1 1  1   1   1    1    1     1     1 ...
  k=1:  1 2  3   4   5    6    7     8     9 ...
  k=2:  1 3  8  16  30   53   91   153   254 ...
  k=3:  1 4 16  42  98  216  455   931  1866 ...
  k=4:  1 5 30  98 268  677 1627  3763  8465 ...
  k=5:  1 6 53 216 677 1906 5039 12747 31180 ...
  ....
As a triangle: the _underlined_ entries add up to the *starred* one, making a symmetric "V", the largest possible at that position:
                    1
                 1     1
              1     2     1
           1     3     3     1
       _1_    4    _8_    4     1
     1    _5_  _16_   16     5     1
  1     6   *30*   42    30     6     1
                 ......
		

Crossrefs

Cf. A347147 (in which the rook can only enter at (1,1), but moves identically).

Programs

Python

T = [[1,1],[1],[1]]  # set T[0][0]=T[1][0]=T[0][1]=T[0,2]=1
print(f"T(0, 0) = {T[0][0]}")
print(f"T(1, 0) = {T[1][0]}")
print(f"T(0, 1) = {T[0][1]}")
print(f"T(2, 0) = {T[2][0]}")
n=2; k=0;
for j in range(54):
    if n == 1:
        T[0].append(1); # set T[0][k+1] to 1
        print(f"T({0}, {k+1}) = {T[0][k+1]}")
        T.append([1]);  # set T[k+2][0] to 1
        n = k+2; k = 0;
        print(f"T({n}, 0) = {T[n][0]}")
        continue;
    n -= 1; k += 1;
    T[n].append(sum(T[n-i][k]+T[n][k-i] for i in range(1,min(n,k)+1)))
    print(f"T({n}, {k}) = {T[n][k]}")

Formula

T(n,k) = 2*(T(n-1,k) + T(n,k-1)) - 3*T(n-1,k-1) - T(n,k-n-1) + T(n-1,k-n), for 1 < n < k; and symmetrically for 1 < k < n; identical to the formula for A347147.

T(n,n) = 2*(T(n-1,n) + T(n,n-1)) - 3*T(n-1,n-1) + 2 = 4*T(n-1,n) - 3*T(n-1,n-1) + 2, for n > 1.