Number of ways to move the king across chess board

[gruba]

Homework Statement

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?

Homework Equations

-Combinatorics

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?

 

[.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.

 

[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.

 

[gruba]

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.

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

 

[PeroK]

Homework Statement

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?

Homework Equations

-Combinatorics

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?

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

 

[Samy_A]

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.

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

 

[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 x⁷y⁷ in the expansion of (1-x-y-xy)^-1.

 

[gruba]

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 x⁷y⁷ in the expansion of (1-x-y-xy)^-1.

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

 

[haruspex]

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

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 N_r,s. Can you see how to write N_r,s as a combination of N_r,s-1, N_r-1,s and N_r-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
N_0,0=1, N_0,s=0 for s>0, N_r,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 x^ry^s 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 N_r,s as the coefficients.