Number of Paths

In the possible paths he could go diagonally zero times, once, twice or thrice.

• If he doesn't go diagonal, he will travel 3 horizontal steps and 3 vertical steps. Possible arrangements of $(v,v,v,h,h,h)$ which is nothing but $\frac{6!}{3!3!}$

• If he goes diagonal once he would have to travel the two horizontal and two vertical. Arrangements of $(v,v,h,h,d)$ , which is nothing but $\frac{5!}{2!2!1!}$ .

• If he goes diagonal twice he would have to travel the one horizontal and one vertical step. Arrangements of $(v,h,d,d)$ , which is nothing but $\frac{4!}{2!1!1!}$ .

• If he goes diagonal thrice there is only one path. $(d,d,d)$

Hence the answer $\boxed{\boxed{63}}$

if number D is n= 0 VVVOOO is 6!/3!3!=20, if then n=1 VVDOO is 5!/2!2!=30, if then n= 2 VDDO 4!/2!=12 if then else n=3 DDD is 1

Then 20+30+12+1=63

Let's label the diagram as if it were a street map.

Let's call the 4 vertical "avenues" a, b, c, d from left to right. Let's call the 4 horizontal "streets" 1, 2, 3, 4 from bottom to top.

So A is at a1 and B is at d4.

Since we can never double back, each point on the graph as 1, 2, or 3 predecessors. The number of ways of reaching it is the sum of the number of ways of reaching the predecessors.

There is just 1 way to reach a1, a2 and b1. Then we can number the rest of it by adding. So that means 3 ways to reach b2. 1 way to reach a3, so 5 ways to reach b3. and so on.

And we end up with these numbers

1..1.. 1...1 1..3.. 5...7 1..5..13..25 1..7..25..63

So there are 63 ways to go from A to B.

to move 1 diagonal is equivalent to move 1 right and 1 down. Suppose that the number movement of right, down and diagonal consecutively k, l and m Case 1: m=0 In this case, 3 rights and 3 downs are required. So, the value is C(6,3) x C(3,3) =20

Case 2: m=1 In this case, 2 rights and 2 downs are required, since 1 diagonal movement is equivalent to 1 right and 1 left. So, the value is C(5,2) x C(3,2) x C(1,1) = 30

Case 3: m=2 In this case, only 1 right and 1 down are required. So, the value is C(4,2) x C(2,1) x C(1,1) = 12

Case 1: m=3 In this case, no right or down movement are required. So, the value is C(3,3)=1

All possibilities: 20+30+12+1 = 63