A364823 Triangle read by rows: T(n,k) = number of possible positions for four connected discs in the game "Connect Four" played on a board with n columns and k rows, 4 <= k <= n.

10, 17, 28, 24, 39, 54, 31, 50, 69, 88, 38, 61, 84, 107, 130, 45, 72, 99, 126, 153, 180, 52, 83, 114, 145, 176, 207, 238, 59, 94, 129, 164, 199, 234, 269, 304, 66, 105, 144, 183, 222, 261, 300, 339, 378, 73, 116, 159, 202, 245, 288, 331, 374, 417, 460

Offset: 4

Author

Felix Huber, Aug 09 2023

Keywords

• nonn
• tabl
• easy

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.

Examples

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

Links

• Wikipedia, Connect Four.

Crossrefs

Cf. A013582, A090224, A212693, A059193.

Programs

Maple

A364823 := proc(n) local k; for k from 4 to n do return 4*k*n - 9*k - 9*n + 18; end do; end proc; seq(A364823(n), n = 4 .. 100);

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