Step1: Consider the number of diagonal moves = 0.

So, total displacement and, thereby, steps to be taken = 14 (7 upward + 7 rightward).

So the path becomes a sequence of 7 "UP"s and 7 "RIGHT" moves. So all the possible paths will be the rearrangement of the moves in that sequence.

Possible Path 1 = UUUUUUURRRRRRR

Possible Path 2 = UUUUUURRRRRRRU and so on...

So, this now becomes a fundamental combinatorics question like "If we have 14 elements of which 7 are of kind A and 7 are of kind B, in how many ways can we arrange them all?". This leads to the answer 14!/(7!7!0!)

Step 2: Number of diagonal moves = 1.

So, total displacement and, thereby, steps to be taken = 13 (6 upward + 6 rightward + 1 diagonal).

This leads to the answer 13!/(6!6!1!)

I hope you notice the pattern of (Total # of moves !)/ (#Right moves! * #Up moves! * #Diagonal_moves!)

Continuing in this fashion, until we reach number of diagonal moves = 8, we get the following partial sums:

3432+12012+16632+11550+4200+756+56+1

= 48639

Hint: This is a Delannoy number .

Solution 1.

Let R, U, and D denotes a right, up, and diagonal move, respectively. Each path can be represented as a string of R, U, and D such that R = U and R+U+2D = 14, or (R, U, D) = (R, R, 7-R), where R = 0, 1, ..., 7. Therefore the number of paths is sum_{R = 0 -> 7} {C(R+7, R, R, 7-R)}, where C(n, a, b, c) = n!/(a! b! c!) is the multinomial coefficient with n = a+b+c. Hence the answer is 7!/(0! 0! 7!)+8!/(1! 1! 6!)+9!/(2! 2! 5!)+10!/(3! 3! 4!)+11!/(4! 4! 3!)+12!/(5! 5! 2!)+13!/(6! 6! 1!)+14!/(7! 7! 0!) = 48639

Solution 2.

Create a 8-by-8 grid of numbers. Enter 1 to the lower left entry of the grid. For each of the other entries, enter the sum of the entries from its left, bottom, and diagonally one entry down and one entry to the left. If an entry from its left, bottom, or diagonally one entry down and one entry to the left is not present, substitute a zero in its place. Starting from the lower left entry and work our way until we get to the upper right entry, we will obtain the following grid:

00001 00015 00113 00575 02241 07183 19825 48639

00001 00013 00085 00377 01289 03653 08989 19825

00001 00011 00061 00231 00681 01683 03653 07183

00001 00009 00041 00129 00321 00681 01289 02241

00001 00007 00025 00063 00129 00231 00377 00575

00001 00005 00013 00025 00041 00061 00085 00113

00001 00003 00005 00007 00009 00011 00013 00015

00001 00001 00001 00001 00001 00001 00001 00001

The number of paths is the entry in the upper right corner of the grid, namely 48639.

It seems everyone is quite good at maths here!

i just found it using recurrence relation

f[x][y]=f[x-1][y]+f[x][y-1]+f[x-1][y-1]

with base case 1.

In mathematics, a Delannoy number D describes the number of paths from the southwest corner (0, 0) of a rectangular grid to the northeast corner (m, n), using only single steps north, northeast, or east. In this array, the numbers in the first row are all one, the numbers in the second row are the odd numbers, the numbers in the third row are the centered square numbers, and the numbers in the fourth row are the centered octahedral numbers. Alternatively, the same numbers can be arranged in a Triangular array resembling Pascal's triangle, also called the tribonacci triangle,[6] in which each number is the sum of the three numbers above it:

        1
      1   1
    1   3   1
  1   5   5   1
1   7  13   7   1

1 9 25 25 9 1 1 11 41 63 41 11 1

you can calculate the dellanoy number by calculating pascal's triangle and just look form*n term in triangle to get answer

The Delannoy numbers $D(m,n)$ count the number of lattice paths from $(0,0)$ to $(m, n)$ in which only north $(0,1)$ , east $(1,0)$ , and northeast $(1, 1)$ steps are allowed.

The Delannoy numbers are given by:

$D(m,n) = \sum\limits_{k=0}^{min(m,n)} {m+n-k \choose m}{m \choose k}$

The question is equivalent to asking for the Delannoy number D(7,7). Hence we have:

$D(7,7) = \sum\limits_{k=0}^{min(7,7)} {7+7-k \choose 7}{7 \choose k}$ = 48639.