A212693 Number of legal 7 X 6 Connect-Four positions after n plies.

1, 7, 49, 238, 1120, 4263, 16422, 54859, 184275, 558186, 1662623, 4568683, 12236101, 30929111, 75437595, 176541259, 394591391, 858218743, 1763883894, 3568259802, 6746155945, 12673345045, 22010823988, 38263228189, 60830813459, 97266114959, 140728569039

Offset

0,2

Comments

Sum of all 43 terms is 4531985219092 as computed by Edelkamp and Kissmann (see link).

Links

John Tromp, Table of n, a(n) for n = 0..42 (copied from the P. Kissmann link)

Dennis Aanstoot, Graph rewriters as components, Univ. of Twente (Netherlands, 2022).

S. Edelkamp and P. Kissmann, Symbolic Classification of General Two-Player Games

Alistair Hartley Folster, Counting reachable positions in a simplified model of connect four, Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 131. 57-65 (2026).

Brady Haran, Connect Four, Numberphile video, 2013.

Johannes Niklas Hartmann, Finding optimal strategies in sequential games with the novel selection monad, arXiv:2105.12514 [cs.AI], 2021.

P. Kissmann, Algorithm Engineering - Symbolische Suche [broken link]

John Tromp, John's Connect Four Playground

2swap, Beating connect 4 with graph theory, YouTube video (2024).

Example

a(3) = 7 * (1*7 + 6*(5/2 + 2)) = 238 because 3 discs played in different columns can be transposed in two ways.

Crossrefs

Cf. A090224 (upper bound), A013582.

Sequence in context: A141783 A181479 A223842 * A223615 A188768 A188757

Adjacent sequences: A212690 A212691 A212692 * A212694 A212695 A212696

Keyword

nonn,fini,full,changed

Author

John Tromp, May 23 2012

Status

approved