\documentclass{article}
\usepackage{fancyhdr}
\usepackage{amsthm}
\usepackage{etoolbox}
\usepackage{verbatim}
\usepackage{enumerate}
\usepackage{amsmath}
\usepackage{algorithmicx}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{amssymb}
\usepackage{tikz}
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8

\begin{document}

{\bf Abstract}
\\\\
How many ways can a King walk around the board and come back to the origin. We give a procedure for computing this for higher dimensional boards highly efficiently. Also, for several low dimensions, up to the board being $\mathbb{Z}^8$, we give conjectured recurrences for the sequences.

{\bf Maple packages and data files}
\\\\
This article is accompanied by the maple package {\tt KW.txt}
and several example inputs and outputs available at

{\tt http://www.math.rutgers.edu/\~ajl213/DrZ/KW.html} 

{\bf Background}
\\\\

Everyone is familiar with chess, combined with the fact that it is played on a discrete board makes it a fun thing to analyze problems related to. However, a real chess board is only 8x8, for all of our analysis, we will instead be moving on an infinite grid of spaces. In particular, we'll be looking at how many of the $8^n$ paths that a king can take in $n$ moves end up coming back to the original square that he started. A similar analysis can be done for knights. This technique can be extended to any movement rule that only allows movement to squares within some finite distance away from where it started. In particular, this puts all of the results in rook theory outside the scope of this approach.


{\bf This Article}
\\

The sequence  in n we will call $x_{d,n}$ will denote the number of walks of length $n$ that a king could take on a $d$-dimensional grid ending where he starts. A move that the king can take is one that moves either -1, 0, or 1 in each coordinate, but he must not stand still during his move. We disallow standing still as a move, both because it is more analogous to chess, and because it causes the problem to become more interesting. 

We use a little trick to compute out a large number of the terms in the sequence, and then, once enough terms are found, we use the procedure FindRec accompanying [Z] found online at 

{\tt http://sites.math.rutgers.edu/~zeilberg/tokhniot/FindRec.txt}

to guess a rational recurrence that is satisfied by the sequence using the Zeilberger algorithm. Since we find that the number of such paths grows exponentially, actually listing out all of the paths to count up the number that have the king coming back to the start is entirely unfeasible. A slightly less dumb, but still quite slow way of trying to compute this sequence is to take the constant term of
\[
\left(\left(\prod_{i=1}^d (z_i +z_i^{-1} +1\right) -1\right)^n
\]

To help us compute $x_{d,n}$ in a much better way, we will instead first consider the number of paths ending at the start that are taken by a lazy king, one which may decide to stand still as a step. Lets call the sequence counting these kind of paths $y_{d,n}$. This lazy king's behavior is much easier to analyze, as all of the motion in each dimension is independent. We can just just consider which of the three options he picks in each dimension, and require that for each of them, he ends up with a total offset of zero. As far as the counting is concerned, this means that we just need to count in one dimension, and then raise that to the number of dimensions. Luckily, the one dimensional lazy king problem is given by the central trinomial coefficients (A002426), it has a generating function given by
\[
\frac{1}{\sqrt{1-2x-3x^2}}
\]
So we can then just take the $n^{th}$ term from that and raise it to the number of dimensions to answer this different counting problem with very little computation.

Now, we go back to the original problem where the king is not allowed to stand still. Summing over all the possible numbers of the lazy king's moves where he actually moved, and spacing those acutal moves out over the $n$ potential moves, we get

\[
y_{d,n} = \sum_{i=0}^n \binom{n}{i}x_{d,i}
\]
Rearranging this for $x_{d,n}$, we get that
\[
x_{d,n} = y_{d,n} - \sum_{i=0}^{n-1} \binom{n}{i} x_{d,n}
\]

To compute the next term of the sequence, we just need to weight earlier terms in the sequence, and subtract them from a very easy to compute quantity. Also great about this approach is that the number of operations that we need to do doesn't go up as the dimension does. Higher dimension is only a tiny headache for the computer in that the operations it does do need to be done on larger numbers. Using this we were able to compute many hundreds of terms in the sequence. This was enough to guess at finite recurrences that are satisfied by this sequence. For example, on the two dimensional chessboard, we get that the sequence satisfies
\begin{align*}
x_{3,n+3} =&\hspace{.15in} 32\frac{(3n+7)(n+1)^2}{(3n+4)(n+3)^2}x_{3,n}\\
&+4\frac{(27n^3+144n^2+248n+139)}{(3n+4)(n+3)^2}x_{3,n+1}\\
&+\frac{(3n+5)(n+2)(3n+8)}{(3n+4)(n+3)^2}x_{3,n+2}\\
\end{align*}
Where $N$ represents the shift operator. For higher dimensions, the recurrences themselves are quite large, and can be found online at:

{\tt http://www.math.rutgers.edu/\~ajl213/DrZ/KingWalks/RecurrenceData.txt}

 We were unfortunately unable to obtain recurrences for dimension higher than eight because even though it was simple to crank out many many terms for those sequences, obtaining a recurrence of such high degree using the existing tools was not feasible.  

%%%scratch
%want sum T_k^d (-1)^(n-k) binom(n,k)
%(prod(x+1+x^{-1}) -1)^n = sum  prod((x+1+x^{-1})^k) (-1)^(n-k) binomial(n,k)
%CT( sum  prod(x+1+x^{-1})^d) (-1)^(n-k) binomial(n,k)) = 
%sum CT(  prod(x+1+x^{-1})^k)^d (-1)^(n-k) binomial(n,k) = 
%sum T_k^d  (-1)^(n-k) binomial(n,k)

\pagebreak
{\bf References}

[Z] Doron Zeilberger {\it The Holonomic Ansatz: I. Foundations} Annals of Combinatorics, Volume 11, Issue 2, (2007) 227-239

\bigskip
\bigskip
\hrule
\bigskip
Andrew Lohr, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen
Rd., Piscataway, NJ 08854-8019, USA. ajl213 at math dot rutgers dot edu; \quad {\tt http://www.math.rutgers.edu/\~{}ajl213/} \quad .
\bigskip
\hrule

\bigskip
\bigskip

{\bf  First Written:  April 22, 2017; This version: August 28, 2017.}.
\end{document}
