# How many routes?

We have an infinite grid of square lattice, with edge length equal to 1. L is a length of a route from one vertex to another. On the way from one vertex to another is allowed to pass along the edge(vertex) a few times. The direction of motion can be changed only at the vertices.

1) How many routes of length L=9 are there from 1 to 2?

2) How many routes of length L=11 are there from 1 to 3?

3) How many routes of length L=m+n+2k are there from 1 to 4?

See picture there: http://i.stack.imgur.com/obKA7.jpg

-

HINT: Let the symbols $L,R,U$, and $D$ represent single steps to the left, right, up, and down, respectively. Each path of length $n$ can then be represented by a string of $n$ symbols, and each string of $n$ symbols represents a path of length $n$. For example, one way of tracing out the yellow path in your picture is $UULDRDRUU$, and another is $ULURDDRUU$. Note that both have one $L$, two $R$’s, four $U$’s, and two $D$’s, just in different orders.

To get from $1$ to $2$ requires at least one $R$ and two $U$’s, and everything else has to cancel out: for each $L,R,U$, or $D$ beyond that there must be an $R,L,D$, or $U$, respectively, to compensate for it. In the case of either tracing of the yellow path, there is one extra $R$ and a compensating $L$, and there are two extra $U$’s and two compensating $D$’s. To count all of the $9$-step paths from $1$ to $2$, begin by setting aside $3$ steps for the one $R$ and two $U$’s needed for a shortest possible path. That leaves $6$ steps that can be chosen arbitrarily, so long as they’re chosen in balanced pairs: an $L$ with an $R$, or a $U$ with a $D$. In other words, in addition to the required $R$ and two $U$’s, you can have:

• $0$ $LR$ pairs and $3$ $UD$ pairs, for a total of $0$ $L$’s, $1$ $R$, $5$ $U$’s, and $3$ $D$’s;

• $1$ $LR$ pair and $2$ $UD$ pairs, for a total of $1$ $L$, $2$ $R$’s, $4$ $U$’s, and $2$ $D$’s;

• $2$ $LR$ pairs and $1$ $UD$ pair, for a total of $2$ $L$’s, $3$ $R$’s, $3$ $U$’s, and $1$ $D$; or

• $3$ $LR$ pairs and $0$ $UD$ pairs, for a total of $3$ $L$’s, $4$ $R$’s, $2$ $U$’s, and $0$ $D$.

In each of these cases the $9$ symbols can be arranged in any order. Thus, there are $$\binom{9}{0,1,5,3}=\frac{9!}{0!1!5!3!}=504$$ paths of the first type listed above, $$\binom{9}{1,2,4,2}=\frac{9!}{1!2!4!2!}=3780$$ of the second type, and so on.

The same sort of analysis will handle not only the second question, but the general case in the third question, at least to the point of writing the total as a sum of multinomial coefficients; this sum can with a little work then be reduced to a product of two binomial coefficients.

-