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

Author

John Tromp, May 23 2012

Keywords

• nonn
• fini
• full
• changed

Comments

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

Examples

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

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

Crossrefs

Cf. A090224 (upper bound), A013582.