0
$\begingroup$

A pawn is placed on the lower left corner square of a standard 8 by 8 chessboard. A 'move' involves moving the pawn, where possible, either one square to the right, one square up, or diagonally one square up and to the right. Using these legitimate moves the pawn is to be moved along a path from the lower left square to the upper right square.

How many such paths are there?

$\endgroup$
  • $\begingroup$ Do you know what Catalan numbers are? $\endgroup$ – Oria Gruber Sep 29 '14 at 12:11
  • 1
    $\begingroup$ Have you tried a smaller example, say $3\times3$? $\endgroup$ – Arthur Sep 29 '14 at 12:11
  • 1
    $\begingroup$ Have you tried answering the question recursively? $\endgroup$ – Yotam D Sep 29 '14 at 12:11
1
$\begingroup$

Here's a rather pedantic method for solving the problem.

There are three types of "pawn" moves:

(x,y) |--> (x+1,y), (x,y+1), (x+1,y+1)

whose counts we label as respectively $m_1,m_2,m_3 \ge 0$.

To go from (1,1) to (8,8) requires:

$$ m_1 + m_3 = 7 $$

$$ m_2 + m_3 = 7 $$

In particular $m_1 = m_2 = 7 - m_3$, and for any particular choice of $m_3$ we have by permutations of the moves, a corresponding number of distinct paths:

$$ \frac{(m_1+m_2+m_3)!}{m_1!m_2!m_3!} $$

Therefore the distinct paths can be counted by letting $m_3 = 0,\ldots,7$ and summing the results of the above multinomial expression.


Now let's consider a less pedantic/more general method of counting paths using the adjacency matrix $A$ of a directed graph, i.e the $n\times n$ 0,1-matrix whose $(i,j)$ entry is 1 when a directed edge goes from node $x_i$ to node $x_j$, and there are $n$ nodes $x_1,\ldots,x_n$ in the digraph.

Then the number of directed paths of length $k$ from $x_i$ to $x_j$ is the $(i,j)$ entry of $A^k$, a fact that forms the background to this previous Math.SE Question.

In order to count the paths of all possible lengths from $x_i$ to $x_j$, we may take the $(i,j)$ entry after summing over all possible powers of $A$, including if we wish the $0$-length paths represented by $A^0=I$. However for the present problem all paths from the lower left hand corner of the board to its upper right hand corner would be between $7$ and $14$ steps long.

Recall that as a geometric series:

$$ I + A + A^2 + A^3 + \ldots = (I-A)^{-1} $$

Let's take the $3\times 3$ board as an illustrating example, since the nine nodes there are more easily written out in matrix form than the sixty-four nodes of the original chess board.

Numbering the nodes $1$ to $9$, by rows starting with the lower left corner, we have the corresponding adjacency matrix:

$$ A = \begin{bmatrix} 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} $$

$$ (I-A)^{-1} = \begin{bmatrix} 1 & 1 & 1 & 1 & 3 & 5 & 1 & 5 & 13 \\ 0 & 1 & 1 & 0 & 1 & 3 & 0 & 1 & 5 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 3 & 5 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 3 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix} $$

Thus there are $13$ paths from corner-to-corner on the $3\times 3$ board, not the eleven cited in the OP's (now removed) Comment on the Question.

$\endgroup$
  • $\begingroup$ If you use a spreadsheet to organize the calculation, you'll discover that there are some common subexpressions caused by $m_1=m_2$. $\endgroup$ – hardmath Sep 29 '14 at 12:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.