Path counting

Parametric equations

On an $m\times n$ grid, every step goes right or up. The shortest paths run from the lower left, $(0,0)$, to the upper right, $(m,n)$. There are $\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$ of them.

Paths that reach $(i,j)$ obey

A neighbor that would fall outside the grid counts as 0, so the left edge and the bottom edge stay 1. The figure does not print these numbers on the nodes. Brightness tracks the count, and the count field also tracks it by circle size.

Interaction

• Right steps m: set how many steps go right. The control runs from 2 to 9
• Up steps n: set how many steps go up. The control runs from 2 to 9
• One path: draw one route as it grows, then start the next route in turn. The route is a sequence of right and up steps. The letters R and U are not printed
• Path overlay: wash routes over the grid. The picture stops at 900 routes. That stop is a drawing limit, not the value of $N(m,n)$
• Count field: a larger circle means more paths reach that node. The count is not printed
• New path: while One path is on, jump to a random route. In the other two modes the picture does not change

What to notice

• A path is one way to choose which $m$ of the $m+n$ steps go right, so $N(m,n)=\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$. Choosing the up steps instead gives the same count, $\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$.
• The corner $(m,n)$ carries that full count. A node $(i,j)$ inside the grid carries $P(i,j)=\left(\genfrac{}{}{0ex}{}{i+j}{i}\right)$, an earlier binomial coefficient, not the whole of row $m+n$.
• This page counts paths. It does not draw Pascal’s triangle, and it does not draw the Catalan paths that stay below a diagonal.

Related

• Pascal’s triangle
• Geometric significance of the binomial expansion
• Catalan numbers

Further reading

• Lattice path (Wikipedia)