You Can Only Walk This Way!

If Mr. Truong just goes up and right, he must walk up $6$ times and walk right $7$ . So, in total, he must walk $13$ little lines of the grid. Every diagonal he walks is a shortcut: indeed, he walks up and right every time he walks up-right. This means that for each up-right line he walks, he's walking a line less than if he walks up and then right.

As the grid has $6$ diagonals, we can reinterpret the problem as follows:

We have $6$ letters $U$ , $7 R's$ and $6 D's$ . In how many ways can we organize the $U's$ and $R's$ ? $\frac { 13! }{ 7!\cdot 6! }$ ; every time we write one $D$ in each setup we have created previously, we erase one $U$ and one $R$ from each one.

Thus, when we write $1 D$ , we have $6 R's$ and $5 D's$ . The number of ways in which we can organize this letters is $\frac { 12! }{ 6!\cdot 5! }$ .

We can continue writing and removig letters until we have $6 D's$ and just $1 R$ .

At the final, we will have the following sum:

$\sum _{ k=0 }^{ 6 }{ \frac { (13-k)! }{ (7-k)!\cdot (6-k)!\cdot k! } }$ , in which $k$ is the number of $D's$ in the setup.

Therefore, when we calculate that sum, the total different routes in which Mr. Truong can go from $A$ to $B$ are $19825$ .

Let Mr.Truong travel $d$ diagonals. The remaining $13-2d$ sides,he travels up or right, which can be done in $\dbinom{13-2d}{7-d}$ ways. The $d$ diagonals can be placed in $\dbinom{13-d}{d}$ ways.

So the total number of ways= $\displaystyle \sum_{d=0}^{6} \dbinom{13-2d}{7-d}\dbinom{13-d}{d}$ .

This summation turns out as $\boxed {19825}$

Let $a_{n,m}$ be the number of different routes for a grid of $n \times m$

We are looking for $a_{7,6}$

We can easily see that : $a_{n,m} = a_{n-1,m} + a_{n,m-1}+ a_{n-1,m-1} \quad \text{ for n, m positive integers } \\ a_{n,0} = a_{0,n} = 1 \quad \text {for n integer}$

With spreadsheet, we can have the result 19825