3
$\begingroup$

enter image description here

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...

$\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
7
$\begingroup$

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
enter image description here

| improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ +1 for OEIS has this sequence Central Delannoy numbers $\endgroup$ – Sayed Mohd Ali Sep 13 '19 at 16:43
0
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.