# The Computational Challenge of Enumerating High-Dimensional Rook Walks

By Manuel Kauers and Doron Zeilberger. (See also Zeilberger's version of this website.)

Below are given experimentally discovered recurrence equations for the main diagonal a(n,n,...,n) of the multivariate rational series

(1 - x1/(1-x1) - x2/(1-x2) - ... - xd/(1-xd))-1 = sumn1...nd a(n1,...,nd) x1n1...x1n1.

The challenge consists of computing the corresponding certificates.

The column maxint refers to the length of the longest integer appearing in the recurrence, measured in decimal digits.

 dimension recurrence initial values order degree maxint 2 file (51b) file 2 1 2dd 3 file (205b) file 3 4 6dd 4 file (706b) file 4 9 12dd 5 file (3kb) file 5 18 31dd 6 file (10kb) file 6 31 51dd 7 file (32kb) file 7 50 94dd 8 file (83kb) file 8 75 149dd 9 file (211kb) file 9 108 236dd 10 file (421kb) file 10 149 306dd 11 file (939kb) file 11 200 462dd 12 file (1.7Mb) file 12 261 609dd

Here is the 500000th term of the 12D-diagonal. It has 6.6Mio decimal digits starting with 3281988146201855739941174675728... and ending with ...0771375698627198709248000.

## Queens Walks

Here we consider the main diagonal of the power series
(1 - x1/(1-x1) - x2/(1-x2) - ... - xd/(1-xd) - x1...xd/(1-x1...xd))-1.

The asymptotic formula for dimension d is then

sqrt(α)/(nπ)((d - 1)/2)φn
for some constants φ and α which depend on the dimension d.

Guessed recurrence equations and asymptotic constants for dimensions up to 5 are as follows.

### Dimension 2

recurrence (order=3, degree=3, maxint: 3 digits) initial values
 parameter minimal poly approximate value φ x^2-12*x+16 10.47 α 256*x^2+400*x-125 0.266907

### Dimension 3

recurrence (order=6, degree=15, maxint: 19 digits) initial values
 parameter minimal poly approximate value φ x^3-69*x^2+183*x-125 66.3 α 24300*x^3+87156*x^2+83232*x-15625 0.1598

### Dimension 4

recurrence (order=11, degree=49, maxint: 74 digits) initial values
 parameter minimal poly approximate value φ x^4-632*x^3+2392*x^2-3040*x+1296 628.2 α 16483714833083-164482823224832*x -77121798336512*x^2-17203445891072*x^3 -37748736*x^4 0.0958

### Dimension 5

recurrence (order=18, degree=133, maxint: 221 digits) initial values
 parameter minimal poly approximate value φ -16807 + 55255*x - 68305*x^2 + 37615*x^3 - 7785*x^4 + x^5 7780.17 α -926912110862037001 + 16156355853887137400*x + 3996548468558029000*x^2 + 289725325976220000*x^3 - 12064954250000*x^4 + 156800000*x^5 0.056

Manuel Kauers