The computational challenge of enumerating high-dimensional rook walks

2010/11/21 by Manuel Kauers, Doron Zeilberger, Kauers, Manuel +1
Computer Science · Mathematics · #Artificial Intelligence in Games #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #Polynomial and algebraic computation #math.CO

paper · pdf · doi:10.48550/arxiv.1011.4671

arxiv created 2010/11/21 · openalex publication_date 2010/11/21 · arxiv updated 2010/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide guessed recurrence equations for the counting sequences of rook paths on d-dimensional chess boards starting at (0..0) and ending at (n..n), where d=2,3,...,12. Our recurrences suggest refined asymptotic formulas of these sequences. Rigorous proofs of the guessed recurrences as well as the suggested asymptotic forms are posed as challenges to the reader.

Related

• Bijective enumeration of rook walks
• Explicit formula for the generating series of diagonal 3D rook paths
• Rook and queen paths with boundaries
• Hyper-bishops, Hyper-rooks, and Hyper-queens: Percentage of Safe Squares on Higher Dimensional Chess Boards
• Counting Knight's Tours through the Randomized Warnsdorff Rule