# Homework Help: Number of ways to move the king across chess board

1. Dec 7, 2015

### gruba

1. The problem statement, all variables and given/known data
On how many ways the king can be moved from the bottom left field to the upper right field on the chess board such that such that for every move it is closer to the upper right field?

2. Relevant equations
-Combinatorics

3. The attempt at a solution
I assume it is diagonal path of $8\times 8$ matrix.
Is there some strict method in combinatorics (exclusion-inclusion, generating functions,...) to prove this?

2. Dec 7, 2015

### .Scott

There's probably more than one way to attack this problem, but I would start with the observation that without diagonal moves, it will take 14 moves, 7 up and 7 across in any order. Then, each time an up is followed by an across or an across is followed by an up, then the move can be replaced by a diagonal move - but only one for each up/across, across/up pair.
If you can program, this would not be difficult to code.

Alternatively: You are computing F(7,7) by walking through each step with an up, diagonal, or across move as follows:

F(X,Y) = F(Y,X)

For any F(X,Y) where X>0 and Y>0:
F(X,Y) = F(X-1,Y) + F(X-1,Y-1) + F(X,Y-1)

F(X,0) = F(0,Y) = 1

So
F(1,1) = F(0,1) + F(0,0) + F(1,0) = 1+1+1 = 3
F(1,2) = F(0,2) + F(0,1) + F(1,1) = 1+1+3 = 5
F(2,1) = F(1,2) = 5
F(2,2) = F(2,1) + F(1,1) + F(1,2) = 5+3+5 = 13
F(3,1) = ...
...
F(7,7) = F(7,6)+F(6,6)+F(6,7) = ...

Not counting the F(X,0) = F(0,Y) = 1, this would require 49 computations. And can also be coded.

3. Dec 7, 2015

### epenguin

H'mm.
Does 'upper right field' mean 1step beyond the diagonal? On the diagonal?mifncan do one can do the other, but is the question that?
At each step you have 3 choices, if that helps.
I guess you could do it for first row, then second and see what pattern suggests itself.

4. Dec 7, 2015

### gruba

Upper right field is the top right field of the entire board (the king is at the bottom left).

5. Dec 7, 2015

### PeroK

I would consider combinations of $r, u, d$ with the appropriate constraints.

6. Dec 7, 2015

### Samy_A

At each step you have 3 choices, until your reach the last column or last row. From then you have only one choice.

7. Dec 8, 2015

### haruspex

A general approach to the problem involves recurrence relations and generating functions. Are you familiar with these, gruba?
That said, it doesn't make it much easier. You end up having to find the coefficient of x7y7 in the expansion of (1-x-y-xy)-1.

8. Dec 8, 2015

### gruba

Could you elaborate on your method with recurrences and generation functions? How did you get the expansion $(1-x-y-xy)^{-1}$?

9. Dec 8, 2015

### haruspex

First, consider the more general question of moving from one corner to the far corner on a r x s rectangle. Let the number of ways of doing this be Nr,s. Can you see how to write Nr,s as a combination of Nr,s-1, Nr-1,s and Nr-1,s-1? That's called a recurrence relation.
We need to supply boundary conditions. I would use:
The relation applies for all r, s >=1
N0,0=1, N0,s=0 for s>0, Nr,0=0 for r>0. You can check this produces the right numbers for r=1 etc.
The next step is to define a generating function $G(x,y)=\Sigma_{r=1,s=1}N_{r,s}x^ry^s$.
Multiplying through the recurrence relation by xrys and summing produces an equation for the generating function. A little careful working through the boundary parts of the sums leads to G=xy(1-x-y-xy)-1.
If we then expand G as a power series in x and y we can read off the values of Nr,s as the coefficients.