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...
$\begingroup$
$\endgroup$
-
5$\begingroup$ Infinite.$\phantom{!}$ $\endgroup$ – greenturtle3141 Sep 13 '19 at 14:19
-
1$\begingroup$ Can the same point be visited more than once? Or each path used just once? $\endgroup$ – Weather Vane Sep 13 '19 at 14:20
-
$\begingroup$ @WeatherVane each path used once and there is no turning back... $\endgroup$ – Pʀıncess Anaya Sep 13 '19 at 14:21
-
$\begingroup$ Well, this is classic combination math question :P $\endgroup$ – Conifers Sep 13 '19 at 15:25
-
2$\begingroup$ @Conifers To be fair, counting paths on triangular grids can be a research-level mathematics problem. $\endgroup$ – Rand al'Thor Sep 13 '19 at 15:46
$\begingroup$
$\endgroup$
My answer is below
Ans: 321
because there is only one way of getting to each of the points in a northerly direction, and also going direct east
$\begingroup$
$\endgroup$
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.
answered Sep 13 '19 at 15:23
-
$\begingroup$ +1 for OEIS has this sequence Central Delannoy numbers $\endgroup$ – Sayed Mohd Ali Sep 13 '19 at 16:43
$\begingroup$
$\endgroup$
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
answered Sep 13 '19 at 14:22
