1

Define an ``allowable path" from a point $(x,y) \in R^2$ to a point $(x',y') \in R^2$ to be a path from $(x,y)$ to $(x',y')$ consisting of a finite sequence of positive, length $1$, horizontal and vertical steps. In particular, there are no allowable paths from $(x,y)$ to $(x',y')$ unless $(x'-x)$ and $(y'-y)$ are both non-negative integers.

Show that there are ${m+n \choose n}$ allowable paths from $(0,0)$ to $(m,n)$ for all $m, n \in Z$.

Try to do this using Pascal's Triangle!

user273581
  • 37
  • I'm sure this has been done before on this site, please use the search box to find an answer. – David Sep 25 '15 at 03:15
  • The last sentence in the OQ is very interesting. If you trace out the path, the number of ways to get from the top $1$ to any element in Pascal's Triangle moving only southwest or southeast (i.e. without backtracking direction) is the number of that element itself! – Hypergeometricx Oct 04 '15 at 16:38

1 Answers1

1

You can encode an allowable path as a word containing $m$ letters X and $n$ letters Y in any order. An X stands for a unit step in $x$-direction, and a Y stands for a unit step in $y$-direction.

Christian Blatter
  • 226,825