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

Table of n, a(n) for n=4..58.

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

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

Crossrefs

Cf. A013582, A090224, A212693, A059193.

Sequence in context: A190771 A034097 A034107 * A019991 A164285 A268183

Adjacent sequences: A364820 A364821 A364822 * A364824 A364825 A364826

Keyword

nonn,tabl,easy

Author

Felix Huber, Aug 09 2023

Status

approved