THE COMPUTATIONAL CHALLENGE OF ENUMERATING HIGH-DIMENSIONAL ROOK WALKS

By Manuel Kauers and Doron Zeilberger


.pdf     LaTeX source file  
Appeared in Advances in Applied Mathematics v. 47(2011), 813-819.
Written: Nov. 21, 2010.
In how many ways can a positively-walking rook travel from the origin to [n,n,...,n] in the d-dimensional (hyper-cubic) lattice? Of course there is no closed-form formula, but for fixed d ( 2 ≤ d ≤ 12) we can get recurrences, and also for fixed n and variable d.

If you could't care less about the number of ways a rook can walk, perhaps you may be ineterested in finding out in how many ways you can pay your d debts, to d different creditors, where you owe each n dollars. It is the same answer! (why?)


Mathematica Output

Important: This article is accompanied by Manuel Kauers' Mathematica output page that has the Rook recurrences for dimensions up to 12 and the Queen recurrences up to 5.

Main Maple Output

The recurrences for dimensions 2 through 9, as well as the initial conditions, can also be viewed in the file ManuelRookRecurrences .
  • Using this file, as well as the Maple program AsyRec the

    input file yields the output file

    that gives the precise asymptotic formulas to order 10 for dimensions 2 through 9.

  • If you want to see the first 50 terms of the rook-walks enumeration sequences for dimension d (2 ≤ d ≤ 9) using the recurrences found by Manuel Kauers' computer, and the initial d values,
    the input file yields the output file


Maple Package For Fixed n and Variable Dimension

The Maple package RookWalks handles this case.

Maple Output For Fixed n and Variable Dimension

If you want to see the first 150 terms of the sequence enumerating positive Rook walks from the origin to [n,n,...,n] in the d-dimensional hyper-cubic lattice for fixed n and variable d, the guessed recurrences, and the implied asymptotic formula,
[whose leading term seems to be
en-1 (nd)!/n!d   ]
for n=1 (n!) to n=4, the

input file yields the output file


Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page