So it's clear that the total number of shortest routes in a lattice path given a $mxn$ grid is $\binom{s}{r}$ where $s$ is the total number of steps, and $r$ is the total number of right steps. But this is simply to easy. So consider instead this question.

Given a shortest path $p$, how does this determine some $r$-element subset of an $s$-element set $A_p$?

Note: Edited for clarification.

  • $\begingroup$ @mjqxxxx I edited it. Forgot to introduce what $r$ & $s$ were. Maybe that provides a little clarification? I'm completely lost though. $\endgroup$ – Azovax Oct 24 '13 at 3:15
  • $\begingroup$ Hm... The way I know that the number of lattice paths is ${s \choose r}$ makes explicit use of the fact that it's an $r$-element subset of a particular set. How did you come across that formula? $\endgroup$ – Eric Stucky Oct 24 '13 at 3:22
  • $\begingroup$ @EricStucky don't know if this helps, but the $s$ and $r$ are really only making things more complicated. $r$ in this case could be either $m$ or $n$, and $s=m+n$. $\endgroup$ – Azovax Oct 24 '13 at 3:26
  • $\begingroup$ That might help, but it doesn't answer the question: how do you know that ${s \choose r}$, or ${m+n \choose n}$ if you prefer, is the number of lattice paths? $\endgroup$ – Eric Stucky Oct 24 '13 at 3:42
  • $\begingroup$ @EricStucky It's because of binomial coefficients, which is proved here $\endgroup$ – Azovax Oct 24 '13 at 3:47

The linked question from the comments explains what the set and the subset are:

The reason is quite simple: you must make a total of $m+n$ moves, consisting of $m$ moves down and $n$ to the right, in any order, and there are $\binom{m+n}m$ ways to choose which of the $m+n$ moves are down (or, equivalently, $\binom{m+n}n$ ways to choose which $n$ of them are to the right).

If you want to use an arbitrary subset $A$, rather than the subset of moves, this is also allowed, you just need a bijection $f$ between that set and the set of moves, then any path corresponds to a $n$-element subset, where $a\in A$ is in the subset iff $f(a)$ moves right.


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.