# How many ways you can go from point A to point B

I know I have drawn the picture badly but can you tell how many ways we can go from point A to point B.

each path used once and no turning back...

• Infinite.$\phantom{!}$ – greenturtle3141 Sep 13 '19 at 14:19
• Can the same point be visited more than once? Or each path used just once? – Weather Vane Sep 13 '19 at 14:20
• @WeatherVane each path used once and there is no turning back... – Pʀıncess Anaya Sep 13 '19 at 14:21
• Well, this is classic combination math question :P – Conifers Sep 13 '19 at 15:25
• @Conifers To be fair, counting paths on triangular grids can be a research-level mathematics problem. – Rand al'Thor Sep 13 '19 at 15:46

Ans: 321
because there is only one way of getting to each of the points in a northerly direction, and also going direct east

Assuming we can go only right and/or up, my answer is (as @SayedMohdAli's answer)

321

which was produced by this C code

#include <stdio.h>

#define MINGRID 2
#define MAXGRID 7

int grid;
int paths;

void recur(int x, int y)
{
if(x == grid - 1 && y == grid - 1) {
paths++;
}
else if(x < grid && y < grid) {
recur(x + 1, y);
recur(x, y + 1);
recur(x + 1, y + 1);
}
}

int main(void)
{
for(grid = MINGRID; grid <= MAXGRID; grid++) {
paths = 0;
recur(0, 0);
printf(">! grid=%d paths=%d  \n", grid, paths);
}
}


along with solutions for other sized grids:

grid=2 paths=3
grid=3 paths=13
grid=4 paths=63
grid=5 paths=321
grid=6 paths=1683
grid=7 paths=8989

and OEIS has this sequence A001850.

Central Delannoy numbers
3,13,63,321,1683,8989
Number of paths from (0,0) to (n,n) in an n X n grid using only steps north, northeast and east (i.e., steps (1,0), (1,1), and (0,1))

although I didn't look it up first!
There doesn't seem to be a clear and simple formula for it.

• +1 for OEIS has this sequence Central Delannoy numbers – Sayed Mohd Ali Sep 13 '19 at 16:43

In a crude mathematical induction applied, I can

move in 3 ways, if there is one square, 31( 9{diagonally} + 11{lateral)} + 11{lateral}) ways, if there are 4 squares ... and so on...

And hence with

16 squares, it is 2^17 - 1 ways