My Math Forum Chessboard Different Routes Problem

 Probability and Statistics Basic Probability and Statistics Math Forum

 January 28th, 2017, 12:54 PM #1 Newbie   Joined: Jan 2017 From: London Posts: 10 Thanks: 0 Chessboard Different Routes Problem On a chessboard, a king is to be allowed to move one square at a time: horizontally to the right, vertically downward, or diagonally to the right and downward. Imagine a reduced 4x4 chessboard, with the king beginning in the top-left square. By how many routes can he reach the bottom right square? By how many routes can a similar journey be made on a full 8x8 chessboard? I tried to find for an answer, but there seemed to be a very large number of possibilities. Can anyone help?
January 28th, 2017, 08:41 PM   #2
Senior Member

Joined: Sep 2015
From: CA

Posts: 1,265
Thanks: 650

Quote:
 Originally Posted by Estermont On a chessboard, a king is to be allowed to move one square at a time: horizontally to the right, vertically downward, or diagonally to the right and downward. Imagine a reduced 4x4 chessboard, with the king beginning in the top-left square. By how many routes can he reach the bottom right square? By how many routes can a similar journey be made on a full 8x8 chessboard? I tried to find for an answer, but there seemed to be a very large number of possibilities. Can anyone help?
Let's label paths as a trinary number
0: right
1: down/right
2: down

We'll look at the $4 \times 4$ matrix and then generalize it to $n \times n$

The following numbers will start at square $(1,1)$ and end at square $(4,4)$

$\begin{matrix} \text{# 1's} &\text{# 0's} &\text{# 2's} &\text{total #}\\ 0 &3 &3 &(6C0)(6C3)=20\\ 1 &2 &2 &(5C1)(4C2)=30\\ 2 &1 &1 &(4C2)(2C1)=12\\ 3 &0 &0 &(3C3) = 1 \end{matrix}$

for a total of $63$ paths leading from $(1,1)$ to $(4,4)$

You should be able to see the pattern in the table.

Generalizing to an $n \times n$ chessboard we would get

$npaths = \displaystyle{\sum _{k=0}^{n-1}} \binom{2 (n-1)-k}{k} \binom{2 (n-1)-2 k}{n-k-1}$

This does have a sort of closed form

$\Large npaths(n) = \binom{2 (n-1)}{n-1} \, _2F_1(1-n,1-n;2-2 n;-1)$

see link below for explanation of

$_2F_1(1-n,1-n;2-2 n;-1)$

At any rate an $8\times 8$ chessboard has $48639$ possible paths to get from top left to bottom right

 February 4th, 2017, 03:26 PM #3 Newbie   Joined: Jan 2017 From: London Posts: 10 Thanks: 0 I understand everything until you get to the point where you say that a pattern can be seen... Could you please explain the pattern and how it leads to what you say after?
February 4th, 2017, 08:39 PM   #4
Senior Member

Joined: Sep 2015
From: CA

Posts: 1,265
Thanks: 650

Quote:
 Originally Posted by Estermont I understand everything until you get to the point where you say that a pattern can be seen... Could you please explain the pattern and how it leads to what you say after?
look at the # of 1's and the total # column in the table

and match up those two binomial coefficient factors with those given in the expression for npaths a bit below that

February 26th, 2017, 06:08 AM   #5
Newbie

Joined: Feb 2017
From: UK

Posts: 1
Thanks: 0

Quote:
 Originally Posted by romsek Let's label paths as a trinary number 0: right 1: down/right 2: down We'll look at the $4 \times 4$ matrix and then generalize it to $n \times n$ The following numbers will start at square $(1,1)$ and end at square $(4,4)$ $\begin{matrix} \text{# 1's} &\text{# 0's} &\text{# 2's} &\text{total #}\\ 0 &3 &3 &(6C0)(6C3)=20\\ 1 &2 &2 &(5C1)(4C2)=30\\ 2 &1 &1 &(4C2)(2C1)=12\\ 3 &0 &0 &(3C3) = 1 \end{matrix}$ for a total of $63$ paths leading from $(1,1)$ to $(4,4)$ You should be able to see the pattern in the table. Generalizing to an $n \times n$ chessboard we would get $npaths = \displaystyle{\sum _{k=0}^{n-1}} \binom{2 (n-1)-k}{k} \binom{2 (n-1)-2 k}{n-k-1}$ This does have a sort of closed form $\Large npaths(n) = \binom{2 (n-1)}{n-1} \, _2F_1(1-n,1-n;2-2 n;-1)$ see link below for explanation of $_2F_1(1-n,1-n;2-2 n;-1)$ At any rate an $8\times 8$ chessboard has $48639$ possible paths to get from top left to bottom right

How did you get the total numbers on the matrix

 Tags chessboard, problem, routes

### on a chessboard how many routes can a king reach the bottom right square

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post wuzhe Math Events 9 June 27th, 2012 11:41 AM wuzhe Algebra 1 August 11th, 2011 10:15 AM jason.spade Math Events 4 May 17th, 2010 10:47 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top