3
$\begingroup$

You are given a bunch of nodes evenly spaced in a rectangular grid. The rectangle is M nodes long and N nodes wide. Node A is in the upper left hand (northwest) corner and node B is at the bottom right hand corner (southeast). From each node you can only move east, south, or diagonally southeast to the next adjacent node (assuming there is an adjacent node that permits moving in that direction). How many different paths are there from A to B?

I only found a brute-force method using a depth first search with a stack. Is there a more efficient algorithm to solve this puzzle? Specifically, I am looking for an algorithm (preferably efficient) that can determine the total number of paths you can take from node A to node B in a grid of evenly spaced nodes of size M x N.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "path"? There are infinitely many paths between A and B. If you mean "shortest path", then there are $\binom{N+M}{M}$. $\endgroup$ – Yuval Filmus Jun 21 '15 at 5:35
  • $\begingroup$ So you have a grid graph? Do you need an enumerator or the set of all paths? $\endgroup$ – Raphael Jun 21 '15 at 7:20
  • $\begingroup$ @yuval-filmus I'd forgotten to mention that from every node you can only move east, south, or southeast to an adjacent node. In this case I don't think there are infinitely many paths to take. If M = N = 2 there are only 3 paths from A to B. $\endgroup$ – MNRC Jun 21 '15 at 9:29
  • $\begingroup$ @Raphael: I'm not familiar with grid graphs. What is an enumerator? I believe the solution is the set of all paths from A to B. $\endgroup$ – MNRC Jun 21 '15 at 9:31
  • 1
    $\begingroup$ What have you tried? Have you tried working out the number of paths for small values of $M,N$ and looking for a pattern? Have you tried writing a recurrence relation and trying to solve it? This is a fine exercise, but we want to help you learn concepts, not do your exercise for you. $\endgroup$ – D.W. Jun 21 '15 at 23:04
4
$\begingroup$

Let $P(i, j)$ be the number of paths from the start node, $(0,0)$, to the destination node, $(i, j)$. Then it's easy to see that $$\begin{align} P(i, 0) &= 1\\ P(0, j) &= 1\\ P(i, j) &= P(i-1,j)+P(i-1,j-1)+P(i, j-1), \text{ if }i,j>0 \end{align}$$ Applying this recursion directly isn't particularly efficient, since you'll wind up making a lot of redundant calls. You could improve this by memoizing the intermediate values: at step $k$, compute and save the values $P(0, k), P(1, k), \dotsc P(k,k)$ and the values $P(k, 0), P(k, 1), \dotsc P(k,k)$. Note that this last series actually doesn't need to be saved at all, since $P(a,b)=P(b,a)$.


For another way (which turns out to be conceptually the same as Yuval's answer), you could observe that a path consists of a collection of steps:

  1. An eastward move, $E$, from node $(i,j)$ to node $(i+1, j)$.
  2. A southward move, $S$, from node $(i,j)$ to node $(i, j+1)$.
  3. A diagonal move, $D$, from node $(i,j)$ to node $(i+1, j+1)$.

So to get from $(0,0)$ to $(i,j)$ we will need to make $i$ moves east and $j$ moves south. Note that each diagonal move will contribute 1 to the eastward moves and 1 to the southward moves. Thus, every path from the origin to node $(i,j)$ can be uniquely described as a sequence of $E, S, D$ where the number of $E$s plus the number of $D$s equals $i$ and the number of $S$s plus the number of $D$s equals $j$. For example, $P(2,2)$ is the number of paths

  1. Using no $D$s: $EESS, ESES, ESSE, SEES, SESE, SSEE$.
  2. Using one $D$: $DES, DSE, EDS, SED, ESD, SED$.
  3. Using two $D$s: $DD$

So we see that $P(2,2)=6+6+1=13$.

Now the number of sequences of three symbols $D,E,S$, in order, with $a$ of the $D$s, $b$ of the $E$s, $c$ of the $S$s, is given by the multinomial coefficient $$ \binom{a+b+c}{a,\ b,\ c}=\frac{(a+b+c)!}{a!\;b!\;c!} $$ and from this and the observations we just made, we'll have, for $i\le j$, $$ P(i, j)=\sum_{k=0}^i\binom{i+j-k}{k,\ i-k,\ j-k}=\sum_{k=0}^i\frac{(i+j-k)!}{k!\;(i-k)!\;\ (j-k)!} $$ where $k$ is the number of $D$ moves, $i$ is the number of $E$ moves and $j$ is the number of $S$ moves. This sum of factorials is also somewhat computationally expensive, but by recognizing that there are some relations among the terms, you can slightly simplify the number of multiplications and divisions involved. Unfortunately, there doesn't appear to be any nice closed form for this sum, unlike the situation where we don't allow diagonal moves, in which case $P(i,j)=\binom{i+j}{i}$.

$\endgroup$
  • $\begingroup$ Its maybe noteworthy that your first solution comes from the domain of Dynamic Programming. $\endgroup$ – mruether Jun 23 '15 at 13:33
  • $\begingroup$ Could I ask what area a question like this falls under? I have taken basic algorithms and discrete math in graduate school, but was unable to solve this problem. Is Yuval's answer a combinatorics solution? Are there any websites or books with similiar kinds of questions? I'd love to be able to solve these types of problems if I come across them. $\endgroup$ – MNRC Jul 16 '15 at 21:32
  • 1
    $\begingroup$ Its basic form, where you don't allow diagonal moves, this is a standard combinatorial exercise, one which has a nice closed form solution. Yuval's solution is also a combinatorial one, using generating functions. These functions should be part of every discrete mathematician's toolkit and are powerful and general enough to well repay the effort to learn them. Best of luck. $\endgroup$ – Rick Decker Jul 17 '15 at 1:23
3
$\begingroup$

The answer is the coefficient of $x^N y^M$ in the generating function $$ \frac{1}{1-x-y-xy}. $$ This is because $$ \frac{1}{1-x-y-xy} = \sum_{\ell=0}^\infty (x+y+xy)^\ell, $$ and every term in the expansion of $(x+y+xy)^\ell$ corresponds to a walk of length $\ell$.

We can also obtain an explicit formula for it: $$ \sum_{t=0}^{\min(N,M)} \frac{(N+M-t)!}{t!(N-t)!(M-t)!}. $$ Here $t$ is the number of diagonal steps.

$\endgroup$
  • $\begingroup$ Can you give me a hint what x and y mean? $\endgroup$ – mruether Jun 23 '15 at 13:22
  • 1
    $\begingroup$ @mruether One of them means "east" and the other "south" (you can choose which is which as you will). $\endgroup$ – Yuval Filmus Jun 23 '15 at 15:39

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.