login
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, 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,5
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).
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.
EXAMPLE
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
......
PROG
(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]}")
CROSSREFS
Cf. A347147 (in which the rook can only enter at (1,1), but moves identically).
Sequence in context: A026692 A114202 A125806 * A202756 A156354 A295205
KEYWORD
nonn,tabl
AUTHOR
Glen Whitney, Aug 21 2021
STATUS
approved