King on a $15 \times 15$ chessboard

Question

A king is placed in the center tile of a $15 \times 15$ chessboard. He can move in the usual ways, 1 move in any direction. In how many ways can he return to his original position if he can make a total of 6 moves in all.

I know that the whole "$15 \times 15$ board" is to throw one off, since he is essentially limited to an $7 \times 7$ board, due to number-of-moves restriction. I also know that the first step has nine possibilities, but from the second step onwards it seems like a mathematical impossibility to consider all moves possible. Could someone please help?

Answer 1

The first step is to list the combinations of moves that can return to start. One is three up and three down. There are ${6 \choose 3}=15$ ways to put those in order. There are other combinations with two types of moves, each of which gives $15$ possibilities. There are also some with three types of moves.

Answer 2

It is the coefficient $x^0y^0$ in the generating function \begin{eqnarray*} \left( \frac{1}{xy}+\frac{1}{x} +\frac{1}{y}+\frac{x}{y}+\frac{y}{x}+x+y+xy \right)^6. \end{eqnarray*}

Answer 3

Hint:

You know the first step is to one of the eight neighboring squares (red), and the last step is from one of those squares. (Call it the "central ring.") So the problem reduces to calculating the number of 4-step paths that lead from a point on the central ring back to a point on the central ring. There are only two categories of cases: The starting point is on an edge or on a corner.

You should be able to count these cases through exhaustive enumeration.

Then use this with the total number of corners and of edge squares, totaling them up.

Answer 4

Instead of thinking of the king moving on a chessboard, we can instead translate the problem into one of walks in a graph. Specifically, consider squares of the board the vertices of the graph, and place an edge between them if they differ by a King move.

Now, the problem becomes "How many closed walks of length 6 are there on this graph." (or depending on your interpretation, length up to 6) Fortunately, this problem has a known solution using adjacency matrices.

I'll let you read up on it by yourself, but essentially, you compute the 6th power of the adjacency matrix of this graph, then look at the entry $(i,i)$, where $i$ is the index of the vertex corresponding to where the king is initially placed.

This can be somewhat cumbersome to compute by hand (I'll let other answers deal with that), but it has the advantage of giving the correct answer wherever the king is initially placed---most other answers break down if the king is on an edge, corner, or one step away from the center, etc. It also generalizes to an arbitrary number of steps.

Answer 5

You can solve the problem recursively as follows. Let $a(i,j,k)$ denote the number of walks from $(i,j)$ to $(0,0)$ with exactly $k$ steps. Then $$ a(i,j,k) = \begin{cases} 0 &\text{if $k < \max(|i|,|j|)$}\\ [i = 0 \land j = 0] &\text{if $k=0$}\\ \displaystyle{\sum_{(d_i,d_j) \in \{-1,0,1\}^2 \setminus \{(0,0)\}} a(i+d_i,j+d_j,k-1)} &\text{otherwise} \end{cases} $$ The resulting values of $a(i,j,6)$ are: \begin{matrix} i\backslash j &-7 &-6 &-5 &-4 &-3 &-2 &-1 &0 &1 &2 &3 &4 &5 &6 &7 \\ \hline -7 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ -6 &0 &1 &6 &21 &50 &90 &126 &141 &126 &90 &50 &21 &6 &1 &0 \\ -5 &0 &6 &30 &96 &210 &360 &486 &540 &486 &360 &210 &96 &30 &6 &0 \\ -4 &0 &21 &96 &306 &660 &1140 &1536 &1716 &1536 &1140 &660 &306 &96 &21 &0 \\ -3 &0 &50 &210 &660 &1370 &2340 &3090 &3460 &3090 &2340 &1370 &660 &210 &50 &0 \\ -2 &0 &90 &360 &1140 &2340 &4035 &5310 &5985 &5310 &4035 &2340 &1140 &360 &90 &0 \\ -1 &0 &126 &486 &1536 &3090 &5310 &6900 &7800 &6900 &5310 &3090 &1536 &486 &126 &0 \\ 0 &0 &141 &540 &1716 &3460 &5985 &7800 &8840 &7800 &5985 &3460 &1716 &540 &141 &0 \\ 1 &0 &126 &486 &1536 &3090 &5310 &6900 &7800 &6900 &5310 &3090 &1536 &486 &126 &0 \\ 2 &0 &90 &360 &1140 &2340 &4035 &5310 &5985 &5310 &4035 &2340 &1140 &360 &90 &0 \\ 3 &0 &50 &210 &660 &1370 &2340 &3090 &3460 &3090 &2340 &1370 &660 &210 &50 &0 \\ 4 &0 &21 &96 &306 &660 &1140 &1536 &1716 &1536 &1140 &660 &306 &96 &21 &0 \\ 5 &0 &6 &30 &96 &210 &360 &486 &540 &486 &360 &210 &96 &30 &6 &0 \\ 6 &0 &1 &6 &21 &50 &90 &126 &141 &126 &90 &50 &21 &6 &1 &0 \\ 7 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 &0 \\ \end{matrix} In particular $a(0,0,6)=8840$.