# Number of paths of length $n$ starting from the origin in the $X-Y$ plane.

I have to find out the number of paths of length $n$ starting from the origin with movements

• $R : (x,y) \rightarrow (x+1,y)$

• $L : (x,y) \rightarrow (x-1,y)$

• $U : (x,y) \rightarrow (x,y+1).$

Also step $R$ is not followed by $L$ and vice-versa.

In a book that I was following has done it in the following way .

I have some problem understanding it.

1. First why $a_{n-1} = b_n$ ?
2. Secondly why should I only adjoin step $R$ in a path of length $(n-1)$ which ends with $R$ ? I may adjoin $U$ to the path to get a path of length $n$.
3. Also the recurrence relation is not clear to me.

Any help will be very helpful.( If any other way of understanding is possible please let me know) Thank you.

• For your first point of confusion, note that before you move at all you can move left right or up with $n$ steps to go. But if you take the first action to go up, then you're on a new point which can now (for the second step) go left right or up, but with only $n-1$ steps left to go. So going up on your first step makes no difference to your current situation, only that you have $1$ less steps left to proceed with – Jihoon Kang Sep 23 '17 at 5:43
• Then it will be same case if I start with $R$ or $L$ ? – hiren_garai Sep 23 '17 at 5:45
• no, because if you take L first, say, then on your next point you can only go U or L again, since according to the rules R is now not allowed. So you're in a different situation – Jihoon Kang Sep 23 '17 at 5:46
• Oh ! I get it . What about other confusions ? – hiren_garai Sep 23 '17 at 5:47

To count $a_n$, the number of paths of length $n$, the author is splitting the set of such paths into the disjoint union of three subsets:

1. The paths ending in U
2. The paths ending in LL, RR or UL
3. The paths ending in UR

Note that the latter two cases combine to count all of the paths ending in L or R, as LR and RL are not permitted.

@Jihoon Kang addressed your first concern. For the remaining two, both points are addressed by counting the three subsets above individually.

First, any path ending in U may be preceded by any legal path of length $n-1$, so there are $a_{n-1}$ paths in the first subset.

Second, given any path of length $n-1$, there is a unique way to complete it such that the path ends with one of LL, RR, or UL. You are correct that it is legal to follow a U with an R, but that would create a path that is not in the second subset, so it is not counted here. The number of paths in this subset is $a_{n-1}$.

Finally, a path ending in UR can be obtained by adding UR to any path of length $n-2$, so there are $a_{n-2}$ paths in this subset.

Since the set of paths of length $n$ is the disjoint union of these three subsets, we get the recurrence $a_n = 2a_{n-1} + a_{n-2}$ by simply summing the sizes of the three subsets.

• Completely ok now !. Thanks @JeremyDover. – hiren_garai Sep 23 '17 at 16:58