OFFSET
2,1
REFERENCES
Donald E. Knuth, The Art of Computer Programming, Vol. 4B: Combinatorial Algorithms, Part 2, Addison-Wesley, 2023, section 7.2.2.2, pp. 289-291.
FORMULA
T(n,k) = T(k,n).
T(2,k) = k + 2.
T(n,2) = n + 2.
EXAMPLE
Array begins (cf. Table 5 in Knuth (2023), section 7.2.2.2, p. 291, where T(n,k) is denoted by Z(m,n)):
n\k| 2 3 4 5 6 7 8 9 10 11 12 ...
-----------------------------------------------------
2 | 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, ...
3 | 5, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, ...
4 | 6, 8, 10, 11, 13, 14, 15, 16, 17, 18, 19, ...
5 | 7, 9, 11, 13, 15, 16, 18, 19, 21, 22, 23, ...
6 | 8, 10, 13, 15, 17, 19, 20, 22, 23, 25, 26, ...
7 | 9, 11, 14, 16, 19, 22, 23, 25, 26, 28, 29, ...
8 | 10, 12, 15, 18, 20, 23, 25, 27, 29, 31, 33, ...
9 | 11, 13, 16, 19, 22, 25, 27, 30, 32, 34, 37, ...
10 | 12, 14, 17, 21, 23, 26, 29, 32, 35, 37, 40, ...
11 | 13, 15, 18, 22, 25, 28, 31, 34, 37, 40, 43, ...
12 | 14, 16, 19, 23, 26, 29, 33, 37, 40, 43, 46, ...
...
T(3,4) = 8 because, no matter how 8 ones are arranged in a 3 X 4 matrix, a 2 X 2 submatrix of ones cannot be avoided (in the left configuration below, for example, the submatrix elements are highlighted by parentheses). 7 ones can avoid such submatrix (right).
.
(1) 0 (1) 1 1 0 1 1
0 1 0 1 0 1 0 1
(1) 1 (1) 0 1 1 0 0
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Paolo Xausa, Sep 13 2024
STATUS
approved