Counting reachable positions in a simplified model of connect four
Journal of Combinatorial Mathematics and Combinatorial Computing · 17.06.2026 · 131 · 57-65
DOI: 10.61091/jcmcc131-04 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Combinatorial Mathematics and Combinatorial Computing, online erschienen am 17.06.2026. Verfasst von Alistair Hartley Folster.
Abstract (Originalsprache)
By eliminating the win condition in the game of Connect Four and extending the board to infinite height, a rich state space of positions is obtained. We investigate the number of positions reachable on an \(n\)-column board after \(k\) color-alternating moves. For fixed \(k\) we demonstrate polynomiality, derive a partial formula for the polynomial coefficients, and precisely characterize the asymptotic behavior as \(n \to \infty\). We then turn our attention to the fixed-\(n\) case and show that, under a natural addition operation, positions reachable in an even number of moves form a monoid with a highly symmetric finite generating set; by examining certain free submonoids, we bound the exponential growth rate as \(k \to \infty\).
Zitieren
APA
Folster, A. H. (2026). Counting reachable positions in a simplified model of connect four. Journal of Combinatorial Mathematics and Combinatorial Computing, 131, 57-65. https://doi.org/10.61091/jcmcc131-04
Vancouver
Folster AH. Counting reachable positions in a simplified model of connect four. Journal of Combinatorial Mathematics and Combinatorial Computing. 2026;131:57-65. doi:10.61091/jcmcc131-04
BibTeX
@article{Folster2026,
author = {Folster, Alistair Hartley},
title = {Counting reachable positions in a simplified model of connect four},
journal = {Journal of Combinatorial Mathematics and Combinatorial Computing},
year = {2026},
volume = {131},
pages = {57--65},
doi = {10.61091/jcmcc131-04}
}
EUVIMED