OFFSET
4,1
COMMENTS
In the game, all these positions can be reached. The most difficult thing is to connect four discs in the top row in the case of n=k. Here are examples for 4 X 4, 5 X 5 and 6 X 6:
. b3 b12 b8 b11 .
b3 b5 b8 b10 . . a3 a12 b7 a11 .
b2 b4 b8 b7 b2 a5 a8 a10 . . b2 b10 a7 a10 .
a2 a4 a8 b6 a2 b4 b7 b9 . . a2 a8 b6 b9 .
b1 b3 a7 a6 b1 a4 a7 a9 . . b1 a6 b5 a9 .
a1 a3 b5 a5 a1 a3 b6 a6 . . a1 b4 a4 a5 .
For n >= 7 any position in the top row can be reached by the following procedure. By repeating the following scheme, a tower of any height up to the second highest row can be built by placing discs alternately:
b4 b3 a4 a3
a1 a2 b1 b2
You can also build a separate tower where you are completely free with at least three discs. While one player places his four discs in the top row, the other moves to these reserve squares. Therefore, any position of four connected discs in the top row can be realized. Example 7 X 7:
. a a a a . .
. b b a a . .
. a a b b . .
. b b a a . .
. a a b b . b
. b b a a . b
. a a b b . b
For vertical positions there are many reserve squares in the other columns, for diagonal and horizontal positions other than in the top row you have additional reserve squares above three of the four discs to connect. For n > k you have further columns with more reserve squares.
LINKS
Wikipedia, Connect Four.
FORMULA
T(n,k) = 4*k*n - 9*k - 9*n + 18, 4 <= k <= n, comprising k*(n-3) = k*n - 3*k horizontal positions, n*(k-3) = k*n - 3*n vertical positions, and 2*(n-3)*(k-3) = 2*k*n - 6*k - 6*n + 18 diagonal positions.
T(n,n) = 4*n^2 - 18*n + 18 = A059193(n-2).
EXAMPLE
The triangle T(n,k) begins:
n/k 4 5 6 7 8 9 10 ...
4: 10
5: 17 28
6: 24 39 54
7: 31 50 69 88
8: 38 61 84 107 130
9: 45 72 99 126 153 180
10: 52 83 114 145 176 207 238
.
.
.
MAPLE
CROSSREFS
KEYWORD
AUTHOR
Felix Huber, Aug 09 2023
STATUS
approved