
Probability and Statistics Basic Probability and Statistics Math Forum 
 LinkBack  Thread Tools  Display Modes 
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 topleft 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: USA Posts: 1,753 Thanks: 896  Quote:
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}^{n1}} \binom{2 (n1)k}{k} \binom{2 (n1)2 k}{nk1}$ This does have a sort of closed form $\Large npaths(n) = \binom{2 (n1)}{n1} \, _2F_1(1n,1n;22 n;1)$ see link below for explanation of $_2F_1(1n,1n;22 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: USA Posts: 1,753 Thanks: 896  Quote:
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:
How did you get the total numbers on the matrix  

Tags 
chessboard, problem, routes 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
a chessboard problem  wuzhe  Math Events  9  June 27th, 2012 12:41 PM 
a chessboard set up problem  wuzhe  Algebra  1  August 11th, 2011 11:15 AM 
A Chessboard Problem  jason.spade  Math Events  4  May 17th, 2010 11:47 AM 